> #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。










....................................................................................................................................................知道原因了 。
{return ((A *)p2)->p - ((A *)p1)->p;}
{return ((A*)p1)->p<((A*)p2)->p?1:-1;}
上面一句的速度是下面的5倍