[PAT-TOP] 1001 Battle Over Cities - Hard Version

cpcs

1001  Battle Over Cities - Hard Version
N个城市，之前有道路相连，有些道路是坏的，修路需要代价。如果一个城市被占领，则所有和它关联的道路都关闭。目标是：选择最重要的（若干）城市——如果它被占领，我们需要很大的修路代价把其他城市连起来。

分析： 问题虽然说了原来图保证连通，但有可能原来就是一个树了，这样占领一些城市，可能会导致，我们根本无法连接剩余城市，这种代价要按照无穷大计算…… 坑就在这里。这个题说白了就是一个kruskal算法的最小生成树问题。 Top level也不太难。

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <string>
   
4. #include <vector>
   
5. #include <algorithm>
   
6. 
   
7. using namespace std;
   
8. 
   
9. struct node {
   
10. int x;
    
11. int y;
    
12. int c;
    
13. };
    
14. 
    
15. int f[505], num[505];
    
16. vector<node> e;
    
17. 
    
18. bool cmp(const node &x, const node &y) {
    
19.         return x.c < y.c;
    
20. }
    
21. 
    
22. int getf(int x) {
    
23.         return (f[x] == x)?x:(f[x] = getf(f[x]));
    
24. }
    
25. 
    
26. bool make(int x,int y) {
    
27.         if ((x = getf(x)) == (y = getf(y))) {
    
28.                 return false;
    
29.         }
    
30.         if (num[x] < num[y]) {
    
31.                 f[x] = y;
    
32.                 num[y] += num[x];
    
33.         }
    
34.         else {
    
35.                 f[y] = x;
    
36.                 num[x] += num[y];
    
37.         }
    
38.         return true;
    
39. }
    
40. 
    
41. int main() {
    
42. int n, m;
    
43.         scanf("%d%d",&n,&m);
    
44.         for (int i = 0; i < m; ++i) {
    
45.                 int x, y, c, p;
    
46.                 scanf("%d%d%d%d",&x, &y, &c, &p);
    
47.                 node temp;
    
48.                 temp.x = x - 1;
    
49.                 temp.y = y - 1;
    
50.                 temp.c = p?0:c;
    
51.                 e.push_back(temp);
    
52.         }
    
53.         sort(e.begin(), e.end(), cmp);
    
54.         vector<int> answer;
    
55.         int now = 1;
    
56.         bool mark = false;
    
57.         for (int i = 0; i < n; ++i) {
    
58.                 int need = n - 2;
    
59.                 int cost = 0;
    
60.                 for (int j = 0; j < n; ++j) {
    
61.                         f[j] = j;
    
62.                         num[j] = 1;
    
63.                 }
    
64.                 for (int j = 0; (need > 0) && (j < m); ++j) {
    
65.                         if ((e[j].x != i) && (e[j].y != i) && make(e[j].x, e[j].y)) {
    
66.                                 --need;
    
67.                                 cost += e[j].c;
    
68.                         }
    
69.                 }
    
70.                 if (need > 0) {
    
71.                         if (!mark) {
    
72.                                 mark = true;
    
73.                                 answer.clear();
    
74.                         }
    
75.                         answer.push_back(i);
    
76.                 }
    
77.                 else if (mark) {
    
78.                 }
    
79.                 else if (cost > now) {
    
80.                         now = cost;
    
81.                         answer.resize(1);
    
82.                         answer[0] = i;
    
83.                 }
    
84.                 else if (cost == now) {
    
85.                         answer.push_back(i);
    
86.                 }
    
87.         }
    
88.         if (answer.empty()) {
    
89.                 puts("0");
    
90.         }
    
91.         else {
    
92.                 for (int i = 0; i < answer.size(); ++i) {
    
93.                         if (i) {
    
94.                                 putchar(' ');
    
95.                         }
    
96.                         printf("%d",answer【i】 + 1);
    
97.                 }
    
98.                 puts("");
    
99.         }
    
100.         return 0;
     
101. }
     

复制代码

丽蓓嘉

感谢cpcs分享~~~