#include<iostream>
#define MAX 11111
using namespace std;
    //ifstream cin("a.in");
    //ofstream cout("a.out");
    int n,f[MAX],ans,pos;
struct A
{
    int p,d;
}a[MAX];
int cmp(const void *p1,const void *p2)
    {return ((A*)p1)->p<((A*)p2)->p?1:-1;}
int gf(int x)
{
    if(f[x]>=0)
        return f[x]=gf(f[x]);
    else return x;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int i,t;
    a[0].p=INT_MAX;
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,-1,sizeof(f));
        for(pos=i=1;i<=n;++i)
            scanf("%d%d",&a[i].p,&a[i].d);
        qsort(a,n+1,sizeof(A),cmp);
        for(ans=0,i=1;i<=n;++i)
            if(t=gf(a[i].d))
                f[t]=t-1,ans+=a[i].p;
        printf("%d\n",ans);
        //cout<<ans<<'\n';
    }
    return 0;
}


并查集写的。别人两位数过的秘密是什么？为什么我用并查集会比别人直接纯贪心要慢很多？我的319MS。

• Re:求三位数到两位数的优化 (1252) shanafan 2011-04-24 15:58:37