008-08-29 17:37
http://acm.pku.edu.cn/JudgeOnline/problem?id=2421
这个题没有做出来，完全归咎于自己没有对最小生成树理解透彻。
题目 ： 最小生成树，然后下面有个数，代表已经修完的边了。。。。。已经修完了，不就是免费了么。。。。我疯了。。。。(不是自己想到的) 而且还看错题了。。。明明让求和。。。我求得是最小的。。。。。
希望下次有点记性。。。。没少干过这事
1 #include <stdio.h>
2 #include <string.h>
3 #include <algorithm>
4 #define max 101
5 using namespace std;
6 int m, n, p[max], dc;
7 struct E{
8 int u, v, w;
9 }e[100000];
10 struct D{
11 int u, v;
12 }d[100000];
13 int find(int x){
14 if(x != p[x])
15 return p[x] = find(p[x]);
16 return p[x];
17 }
18 int cmp(E a, E b){
19 return a.w > b.w;
20 }
21 int main(){
22 int i, j, u, v, w, sum, t, c, tc, min;
23 while(scanf("%d", &m) != -1){
24 n = dc = c = sum = 0;
25 for(i = 0; i < max; i++)
26 p[i] = i;
27 for(i = 1; i <= m; i++)
28 for(j = 1; j <= m; j++){
29 scanf("%d", &t);
30 if(j > i && t){
31 e[c].u = i;
32 e[c].v = j;
33 e[c++].w = t;
34 }
35 }
36 scanf("%d", &dc);
37 for(i = 0; i < dc; i++){
38 scanf("%d%d", &u, &v);
39 for(j = 0; j < c; j++)
40 if(u == e[j].u && v == e[j].v || v == e[j].u && u == e[j].v)
41 e[j].w = 0;
42 }
43 tc = c;
44 make_heap(e, e + c, cmp);
45 for(n = 1; n < m; tc--){
46 if((u = find(e[0].u)) != (v = find(e[0].v))){
47 n++;
48 p[u] = v;
49 sum += e[0].w;
50 }
51 pop_heap(e, e + tc, cmp);
52 }
53 printf("%d\n", sum);
54 }
55 return 0;
56 }