BNUOJ 26229 Red/Blue Spanning Tree

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 1010;
18 struct arc{
19     int u,v;
20     char color;
21     arc(int x = 0,int y = 0,char ch = ‘#‘):u(x),v(y),color(ch){}
22 };
23 bool cmp1(const arc &x,const arc &y){
24     return x.color < y.color;
25 }
26 bool cmp2(const arc &x,const arc &y){
27     return x.color > y.color;
28 }
29 arc e[1100010];
30 int n,m,k,uf[maxn];
31 int Find(int x){
32     if(x != uf[x]){
33         uf[x] = Find(uf[x]);
34     }
35     return uf[x];
36 }
37 void kruskal(int &cnt,char ch){
38     if(ch == ‘B‘) sort(e,e+m,cmp1);
39     else sort(e,e+m,cmp2);
40     int i,j,tx,ty;
41     for(i = 0; i <= n; i++) uf[i] = i;
42     for(cnt = i = 0; i < m; i++){
43         tx = Find(e[i].u);
44         ty = Find(e[i].v);
45         if(tx != ty){
46             uf[tx] = ty;
47             if(e[i].color == ‘B‘) cnt++;
48         }
49     }
50 }
51 int main() {
52     int i,j,u,v,x,y;
53     char s[5];
54     while(scanf("%d %d %d",&n,&m,&k),n||m||k){
55         for(i = 0; i < m; i++){
56             scanf("%s %d %d",s,&u,&v);
57             e[i] = arc(u,v,s[0]);
58         }
59         kruskal(x,‘R‘);
60         kruskal(y,‘B‘);
61         if(k >= x && k <= y) puts("1");
62         else puts("0");
63     }
64     return 0;
65 }

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<map>
 5 #include<queue>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 const int maxN = 2100;
10 bool vis[maxN];
11 
12 struct node{
13     int x, y;
14 }p[maxN * 100];
15 
16 int find(int u,int *f) {
17     if(f[u] == u)
18         return u;
19     return f[u] = find(f[u], f);
20 }
21 bool fun(int u,int v,int *f) {
22     int px = find(u, f), py = find(v, f);
23     if(px != py) {
24         f[px] = py;
25         return true;
26     }
27     return false;
28 }
29 
30 int main() {
31     int N, M, K;
32     while(scanf("%d%d%d", &N, &M, &K) && (N + M + K)) {
33         int f1[maxN], f2[maxN], f3[maxN], num = 0;
34         for(int i = 0;i <= N;++ i)
35             f1[i] = f2[i] = f3[i] = i;
36         for(int i = 0;i < M; ++ i) {
37             char s[10];
38             int u, v;
39             scanf("%s%d%d", s, &u, &v);
40             if(s[0] == ‘R‘)
41                 fun(u, v, f2);
42             else {
43                 p[num].x = u;
44                 p[num ++].y = v;
45             }
46         }
47         memset(vis, 0, sizeof(vis));
48         int sum = 0, ans = 0;
49         for(int i = 1;i <= N; ++ i) {
50             int px = find(i, f2);
51             if(!vis[px]) {
52                 sum ++;
53                 vis[px] = true;
54             }
55         }
56         for(int i = 0;i < num; ++ i)
57             if(fun(p[i].x, p[i].y, f2)) {
58                 sum --;
59                 K --;
60                 fun(p[i].x, p[i].y, f3);
61                 p[i].x = p[i].y = -1;
62             }
63         int flag = 0;
64         if(sum == 1 && K >= 0) {
65             for(int i = 0;i < num && K > 0; ++ i)
66                 if(p[i].x > 0 && fun(p[i].x, p[i].y, f3)) {
67                     K --;
68                     fun(p[i].x, p[i].y, f2);
69                 }
70         }
71         if(sum == 1 && K == 0)flag = 1;
72         printf("%d\n", flag);
73     }
74 }