M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

TOJ 3446.Money Matters 并查集,路径压缩

        题目大意是N个人互相有债a[i](正的表示别人欠钱,否则表示自己欠别人钱,a[i]的和保证为0),但是这N个人只有朋友间才能互相算帐,现在给出N个人的债,并且给出M个关系,即谁和谁是朋友,最后问有没有可能所有人都把帐算清。


Sample Input 1:                         Sample Input 2:

5    3                                            4     2
100                                              15
-75                                               20
-25                                              -10
-42                                              -15
42                                                0  2
0 1                                               1  3
1 2
3 4

Sample Output 1:                       Sample Output  2:

POSSIBLE                                    IMPOSSILBE

 思路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");
}








posted on 2010-07-05 21:08 M.J 阅读(217) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理