p1838.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 16001;
const int mo[4][2] = {-1,0,1,0,0,-1,0,1};
struct point{ int x,y; };
int ans[MAXN],parent[MAXN],rank[MAXN],vist[MAXN];
point a[MAXN];
int n,g,k;
bool cmp(point a,point b){ return a.x < b.x || a.x == b.x && a.y < b.y; }
void makeset(int x){
    parent[x] = x;
    rank[x] = 0;
    vist[x] = 1;
}
int find(int x){
    if(x == -1 || x >= MAXN) return -1;
    else{
        if(parent[x] != -1 && parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
}
int unionset(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y) return x;
    if(x == -1) return y;
    if(y == -1) return x;
    if(rank[x] > rank[y]){
        parent[y] = x;
        vist[x] += vist[y];
        return x;
    }
    else{
        parent[x] = y;
        vist[y] += vist[x];
        if(rank[x] == rank[y]) ++rank[y];
        return y;
    }
}

int main(){
    memset(ans,sizeof(ans),0);
    memset(a,sizeof(a),0);
    cin >> n >> k;
    for(int i = 0;i < n;++i){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a,a+n,cmp);
//    for(int i = 0;i < n;++i) cout << i << " " << a[i].x << " " << a[i].y << endl;
    for(int i = 0;i < n;++i) makeset(i);
    int i,j(0);
    for(i = 1;i < n;++i){
        for(;j < n && a[j].x < a[i].x - 1;++j);
        if(a[i].x == a[i-1].x && a[i].y - 1 == a[i-1].y) unionset(i,i-1);
        for(;a[i].x - a[j].x == 1 && a[j].y < a[i].y;++j);
        if(a[i].x - a[j].x == 1 && a[j].y == a[i].y) unionset(i,j);
    }
    for(int i = 0;i < n;++i) if(parent[i] == i) ans[g++] = vist[i];
    sort(ans,ans+g);
//    for(i = 0;i < g;++i) cout << ans[i] << endl;
    int res = 0;
    for(int i = 0;i < k && i < n;++i) res += ans[g-i-1];
    cout << res << endl;
}