COJ1241(数字序列)

并查集的题，食物链模型。

题目大意：已知关于n个数的m条信息，信息有两类，一类是已知Ai比Aj大K，另一类是已知Ai为K，问是否能从这m条信息中唯一确定这n个数，或者能推出矛盾。

View Code

 1 #include <stdio.h>
 2 #define N 10001
 3 #define M 20001
 4 int p[N],c[N],v[N];
 5 int a[M],b[M],cnt;
 6 char vis[N];
 7 int n,m;
 8 void make_set()
 9 {
10     int i;
11     for(i=0;i<n;i++)    p[i]=i,c[i]=0,vis[i]=0;
12 }
13 int find_set(int i)
14 {
15     int pi=p[i];
16     if(i!=pi)   p[i]=find_set(p[i]);
17     if(pi!=p[i])    c[i]+=c[pi];
18     return p[i];
19 }
20 void union_set(int i,int j,int d)
21 {
22     int pi=find_set(i),pj=find_set(j);
23     p[pi]=pj;
24     c[pi]=-c[i]+d+c[j];
25 }
26 int main()
27 {
28     int i,j,k,d;
29     char ch,RE,WA;
30     while(~scanf("%d%d",&n,&m))
31     {
32         make_set();
33         RE=WA=0;
34         for(k=cnt=0;k<m;)
35         {
36             scanf("%c",&ch);
37             if(ch=='B')
38             {
39                 k++;
40                 scanf("%d%d%d",&i,&j,&d);
41                 i--,j--;
42                 if(find_set(i)!=find_set(j))    union_set(i,j,d);
43                 else if(c[i]-c[j]!=d)   RE=1;
44             }
45             else if(ch=='S')
46             {
47                 k++;
48                 scanf("%d%d",&j,&d),j--;
49                 a[cnt]=j,b[cnt++]=d;
50             }
51         }
52         for(i=0;i<n;i++)    find_set(i);
53         for(i=0;!RE&&i<cnt;i++)
54         {
55             k=a[i];
56             d=b[i];;
57             j=find_set(k);
58             if(!vis[j])
59             {
60                 vis[j]=1;
61                 v[j]=d-c[k];
62             }
63             else if(v[j]!=d-c[k])   RE=1;
64         }
65         for(i=0;!RE&&!WA&&i<n;i++)  if(!vis[find_set(i)])   WA=1;
66         if(RE)  puts("RE");
67         else if(WA) puts("WA");
68         else    puts("AC");
69     }
70     return 0;
71 }