poj 1838

时间：2014-09-07 23:45:46 阅读：486 评论：0 收藏：0 [点我收藏+]

F - Banana

Time Limit:1000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64u

Description

Consider a tropical forrest, represented as a matrix. The cell from the right top corner of the matrix has the coordinates (1,1), and the coordinates of the other cells are determinated by the row and the column on which the cell is. In some cells of the matrix are placed banana trees; a cell can contain no more than a banana tree. More banana trees which are neighbours on horizontal or vertical form a region of banana trees. In this kind of region, monkey CEKILI is moving easily, with her well-known agility, from a banana tree to another.
CEKILI is eager and the bananas from a single region are not enough for her. Tarzan wants to help his friend. For that, he may connect exactly k banana tree regions knoting more lianas and so CEKILI could move from a region to another using lianas. Obviously, Tarzan must choose the regions so that the total number of banana trees from those k regions must be maximum.

Detemine maximum number of banana trees which Tarzan can obtain connecting exactly k regions.

Input

The input has the following structure:
Nr K
x(1) y(1)
y(2) y(2)
...
x(Nr) y(Nr)
Nr is the number of banana trees. K is the number of zones which can be connected. x(i) is the row of the i-th banana tree, while y(i) is the column of the i-th banana tree.
There are Constraints:
• 1 <= Nr <= 16000;
• 1 <= x(i), y(i) <= 10000;
• In the tests used for grading k will never be bigger than the number of regions;
• Two positions are horizontally neighbours if they are on the same row and consecutive columns, respectively vertically neighbours if they are on the same column and on consecutive rows.

Output

The output will contain on the first line the maximum number of banana trees that can be obtained by connecting the k regions.

Sample Input

Sample Output

9

并查集吧 不知道为什么放在DP专题里

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll __int64
#define MAXN 16000
#define INF 0x7ffffff
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
struct Point
{
    int x,y;
    int id;
};
Point p[16000+10];
int  fa[16000+10];
int num[16000+10];
int cnt[16000+10];
int n;
int cmpx(Point a,Point b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
int cmpy(Point a,Point b)
{
    if(a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
int find(int a)
{
    if(fa[a]!=a) fa[a]=find(fa[a]);
    return fa[a];
}

void bincha(int a,int b)
{
    int x=find(a);
    int y=find(b);
    if(x==y) return ;
    fa[x]=fa[y];
    cnt[y]+=cnt[x];
    cnt[x]=0;
}
int main()
{
    int m;
    int i,j;
    while(cin>>n>>m)
    {

        for(i=1;i<=n;i++)
        {
            cnt[i]=1;
            fa[i]=p[i].id=i;
            scanf("%d%d",&p[i].x,&p[i].y);
        }
        sort(p+1,p+n+1,cmpx);
        for(i=1;i<n;i++)
        {
            if(p[i].x==p[i+1].x&&p[i+1].y-p[i].y==1&&fa[p[i+1].id]!=fa[p[i].id])
            {
               int pre=fa[p[i].id];
               int pre1=fa[p[i+1].id];
               fa[p[i+1].id]=fa[p[i].id];
               cnt[pre]+=cnt[pre1];
               cnt[pre1]=0;
            }
        }
        sort(p+1,p+n+1,cmpy);
        for(i=1;i<n;i++)
        {
            if(p[i].y==p[i+1].y&&p[i+1].x-p[i].x==1&&fa[p[i+1].id]!=fa[p[i].id])
            {
               bincha(p[i+1].id,p[i].id);
            }

        }
        j=0;
        for(i=1;i<=n;i++)
        {
            if(cnt[i]!=0)
            {
                num[j++]=cnt[i];
            }
        }
        sort(num,num+j);        
        j--;
        int ans=0;
        while(m--)
        {
            ans+=num[j--];
        }
        cout<<ans<<endl;
    }
    return 0;
}

poj 1838

原文：http://www.cnblogs.com/sola1994/p/3960931.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)