POJ-1182 食物链

食物链

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 113506		Accepted: 34507

Description

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

Input

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

Output

只有一个整数，表示假话的数目。

Sample Input

Sample Output

Source

Noi 01

[Submit] [Go Back] [Status] [Discuss]

思路

　　和上面D题一样，画出向量图推出关系式之后都能直接用带权并查集解决

CODE

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <assert.h>
  5 #include <iostream>
  6 
  7 #define dbg(x) cout << #x << "=" << x << endl
  8 
  9 using namespace std;
 10 typedef long long LL;
 11 
 12 template<class T>inline void read(T &res)
 13 {
 14     char c;T flag=1;
 15     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 16     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 17 }
 18 
 19 namespace _buff {
 20     const size_t BUFF = 1 << 19;
 21     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 22     char getc() {
 23         if (ib == ie) {
 24             ib = ibuf;
 25             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 26         }
 27         return ib == ie ? -1 : *ib++;
 28     }
 29 }
 30 
 31 int qread() {
 32     using namespace _buff;
 33     int ret = 0;
 34     bool pos = true;
 35     char c = getc();
 36     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 37         assert(~c);
 38     }
 39     if (c == '-') {
 40         pos = false;
 41         c = getc();
 42     }
 43     for (; c >= '0' && c <= '9'; c = getc()) {
 44         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 45     }
 46     return pos ? ret : -ret;
 47 }
 48 
 49 const int maxn = 50007;
 50 
 51 int fa[maxn];
 52 int n,m,ans,cnt;
 53 bool vis[maxn];
 54 int a[maxn];
 55 int _rank[maxn];
 56 //vector <int> v;
 57 
 58 void init()
 59 {
 60     for(int i = 1; i <= n; i++) {
 61         fa[i] = i;
 62         _rank[i] = 0;
 63     }
 64 }
 65 
 66 int fid(int x)
 67 {
 68     int r;
 69     if(x == fa[x])
 70         return x;
 71     r = fa[x];
 72     fa[x] = fid(r);
 73     _rank[x] = (_rank[x] + _rank[r]) % 3;
 74     return fa[x];
 75 }
 76 
 77 void join(int r1, int r2)///合并
 78 {
 79     int fidroot1 = fid(r1), fidroot2 = fid(r2);
 80     int root = min(fidroot1, fidroot2);
 81     if(fidroot1 != fidroot2) {
 82         fa[fidroot1] = root;
 83         fa[fidroot2] = root;
 84     }
 85 }
 86 
 87 int main()
 88 {
 89     int k;
 90     ans = 0;
 91     cin >> n >> k;
 92     init();
 93     while(k--) {
 94         int d,x,y;
 95         scanf("%d %d %d",&d, &x, &y);
 96         int fx = fid(x), fy = fid(y);
 97         if(x > n || y > n) {
 98             ++ans;
 99             continue;
100         }
101         if(d == 2) {
102             if(x == y) {
103                 ++ans;
104                 continue;
105             }
106         }
107         if(fx != fy) {
108             fa[fy] = fx;
109             _rank[fy] = (_rank[x] - _rank[y] + d+2) % 3;
110             //printf("_rank[%d]:%d
",fa[y],_rank[fy]);
111         }
112         else {
113             if(d == 1) {
114                // printf("_rank[%d]:%d
",fa[x],_rank[fx]);
115                 //printf("_rank[%d]:%d
",fa[y],_rank[fy]);
116                 if(_rank[x] != _rank[y]) {
117                     ++ans;
118                 }
119             }
120             else {
121                // printf("_rank[%d]:%d
",fa[x],_rank[fx]);
122                // printf("_rank[%d]:%d
",fa[y],_rank[fy]);
123                 if((3 + _rank[y] - _rank[x])%3 != d - 1) {
124                     ++ans;
125                 }
126             }
127         }
128         //dbg(ans);
129     }
130     cout << ans << endl;
131     return 0;
132 }

View Code