M.J的blog

 思路1：
              每输入一个关系，合并，最后从1到N，对于每一个人，找出它们的祖先，将他们的债debt加到祖先的debt
              上。通俗的讲，就是每个集合的成员都将自己的debt加到祖先上，自己归0，最后看祖先的值是否为0；
              最后在从1到N扫一遍如果有debt不为0的，输出“IMPOSSIBLE”，否则“POSSIBLE”；
              缺点：复杂度高，查询复杂度*N，最后勉强过了，时间0.63s
思路2：
              路径压缩，每输入一个关系，合并。最后从1到N，如果 i 的debt不为0，从 i 到 i 的祖先的路径不断压缩直到
              祖先，这样虽然仍然是N次操作，但由于在压缩过程中大部分成员debt归0，故实际上进行操作的次数远小于N.
              最后时间为0.11,比起上一种方法有了很大提高
Code 1:

#include <cstdio>
#include <cstring>
struct Node{
        int father,v,num;
}a[10002];
int find(int n){
        int tep,m = n;
        while(n != a[n].father)
                n = a[n].father;
        while(m != n){
                tep = a[n].father;
                a[n].father = n;
                m = tep;
        }
        return n;
}
void Union(int root1,int root2){
        int t1,t2;
        t1 = find(root1),t2 = find(root2);
        if(t1 == t2) return ;
        else{
                if(a[t1].v > a[t2].v){
                        a[t1].v += a[t2].v;
                        a[t2].father = t1;
                }
                else{
                        a[t2].v += a[t1].v;
                        a[t1].father = t2;
                }
        }
}
int main()
{
        int n,m,i,j;
        bool flag = false;
        scanf("%d%d",&n,&m);
        for(i = 0;i < n; ++i){
                a[i].father = i,a[i].v = 0;
                scanf("%d",&a[i].num);
        }
        while(m--){
                scanf("%d%d",&i,&j);
                Union(i,j);
        }
        for(i = 0;i < n; ++i){
                int tep = find(i);
                int tt = a[i].num;
                a[i].num -= tt;
                a[tep].num += tt;
        }
        for(i = 0;i < n; i++)
                if(a[i].num != 0){
                        flag = true;
                        break;
                }
        if(flag) printf("IMPOSSIBLE\n");
        else     printf("POSSIBLE\n");
}


Code 2:


#include <cstdio>
#include <cstring>
struct Node{
        int father,v,num;
}a[10002];
int find(int n){
        int m = n,tep;
        while(n != a[n].father)
                n = a[n].father;
        while(m != n){
                tep = a[m].father;
                int tt = a[m].num;
                a[m].num -= tt;
                a[tep].num += tt;
                a[m].father = n;
                m = tep;
        }
        return n;
}
void Union(int root1,int root2){
        int t1,t2;
        t1 = find(root1),t2 = find(root2);
        if(t1 == t2) return ;
        else{
                if(a[t1].v > a[t2].v){
                        a[t1].v += a[t2].v;
                        a[t2].father = t1;
                }
                else{
                        a[t2].v += a[t1].v;
                        a[t1].father = t2;
                }
        }
}
int main()
{
        int n,m,i,j;
        bool flag = false;
        scanf("%d%d",&n,&m);
        for(i = 0;i < n; ++i){
                a[i].father = i,a[i].v = 0;
                scanf("%d",&a[i].num);
        }
        while(m--){
                scanf("%d%d",&i,&j);
                Union(i,j);
        }
        for(i = 0;i < n; ++i)
             if(a[i].num != 0) find(i);
        for(i = 0;i < n; i++)
                if(a[i].num != 0){
                        flag = true;
                        break;
                }
        if(flag) printf("IMPOSSIBLE\n");
        else     printf("POSSIBLE\n");
}