M.J的blog

 思路1：
              每輸入一個關(guān)系，合并，最后從1到N，對于每一個人，找出它們的祖先，將他們的債debt加到祖先的debt
              上。通俗的講，就是每個集合的成員都將自己的debt加到祖先上，自己歸0，最后看祖先的值是否為0；
              最后在從1到N掃一遍如果有debt不為0的，輸出“IMPOSSIBLE”，否則“POSSIBLE”；
              缺點：復(fù)雜度高，查詢復(fù)雜度*N，最后勉強過了，時間0.63s
思路2：
              路徑壓縮，每輸入一個關(guān)系，合并。最后從1到N，如果 i 的debt不為0，從 i 到 i 的祖先的路徑不斷壓縮直到
              祖先，這樣雖然仍然是N次操作，但由于在壓縮過程中大部分成員debt歸0，故實際上進行操作的次數(shù)遠小于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");
}