Hdu 4263 Red/Blue Spanning Tree<kruskal？ >

题意：

给出n个点和m条边<边是蓝色或者红色>的信息..问能不能组成一棵有k条蓝边的树..

思路：

求出尽量多地加蓝边可以加多少条..bl

然后求出尽量多地加红边可以加多少条..re

如果k是在bl和re间就是1 否则是0

Tips：

可以用kruskal也可以之间建树..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 #define clr(x) memset(x, 0, sizeof(x))
 7 int n, m, k;
 8 
 9 int f[10510];
10 int find(int x)
11 {
12     return f[x] == x?x:f[x] = find(f[x]);
13 }
14 
15 struct Edge
16 {
17     int u, v;
18     char col;
19 }edge[1100005];
20 
21 int cmp1(Edge a, Edge b)
22 {
23     return a.col < b.col;
24 }
25 
26 int cmp2(Edge a, Edge b)
27 {
28     return a.col > b.col;
29 }
30 
31 int solve(bool flag)
32 {
33     int ans = 0;
34     for(int i = 0; i <= n; ++i)
35         f[i] = i;
36 
37     if(flag)
38         sort(edge, edge+m, cmp1);
39     else
40         sort(edge, edge+m, cmp2);
41 
42     for(int i = 0; i < m; ++i) {
43         int xx = find(edge[i].u), yy = find(edge[i].v);
44         if(xx != yy){
45             f[xx] = yy;
46             if(edge[i].col == 'B')
47             ans++;
48         }
49     }
50     return ans;
51 }
52 
53 int main()
54 {
55     int i, j;
56     int bl, re;
57     while(scanf("%d %d %d", &n, &m, &k) != EOF)
58     {
59         if(n == 0 && m == 0 && k == 0) break;
60         bl = re = 0;
61 
62         for(i = 0; i < m; ++i){
63             getchar();
64             scanf("%c%d%d", &edge[i].col, &edge[i].u, &edge[i].v);
65         }
66 
67         bl = solve(true);
68         re = solve(false);
69         if(k <= bl && k >= re) puts("1");
70         else puts("0");
71     }
72     return 0;
73 }

其实不排序都可以..

只要是符合条件的且不形成环的..就加进生成树里..

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 #define clr(x) memset(x, 0, sizeof(x))
 7 int n, m, k;
 8 
 9 int f[10510];
10 int find(int x)
11 {
12     return f[x] == x?x:f[x] = find(f[x]);
13 }
14 
15 struct Edge
16 {
17     int u, v;
18     char col;
19 }edge[1100005];
20 
21 int solve(bool flag)
22 {
23     int ans = 0;
24     char cc;
25     for(int i = 0; i <= n; ++i)
26         f[i] = i;
27 
28     if(flag)
29         cc = 'B';
30     else
31         cc = 'R';
32 
33     for(int i = 0; i < m; ++i)
34     if(edge[i].col == cc){
35         int xx = find(edge[i].u), yy = find(edge[i].v);
36         if(xx != yy){
37             f[xx] = yy;
38             ans++;
39         }
40     }
41     return ans;
42 }
43 
44 int main()
45 {
46     int i, j;
47     int bl, re;
48     while(scanf("%d %d %d", &n, &m, &k) != EOF)
49     {
50         if(n == 0 && m == 0 && k == 0) break;
51         bl = re = 0;
52 
53         for(i = 0; i < m; ++i){
54             getchar();
55             scanf("%c%d%d", &edge[i].col, &edge[i].u, &edge[i].v);
56         }
57 
58         bl = solve(true);
59         re = solve(false);
60         if(k <= bl && k >= n-1-re) puts("1");
61         else puts("0");
62     }
63     return 0;
64 }