POJ 2421 Constructing Roads 最小生成樹

POJ 2421 Constructing Roads 最小生成樹

題意：還是給你n個點，然後求最小生成樹。特殊之處在於有一些點之間已經連上了邊。

思路：對於已經有邊的點，特殊標記一下，加邊的時候把這些邊的權值賦值為0即可。這樣就可以既保證這些邊一定存在，又保證了所求的結果正確。

代碼：

1. #include
2. #include
3. #include
4. #include
5. #include
6. using namespace std;
7.  
8. #define CLR(arr,val) memset(arr,val,sizeof(arr))
9. const int N = 110;
10. int father[N];
11. struct edge{
12. int lp,rp,value;
13. }ee[N*N];
14. int map[N][N],flag[N][N],numedge,n;
15. bool cmp(edge a,edge b){
16. return a.value < b.value;
17. }
18. int find(int x){
19. if(x == father[x])
20. return father[x];
21. return find(father[x]);
22. }
23. bool Union_Set(int x,int y){
24. int fx = find(x);
25. int fy = find(y);
26. if(fx == fy){
27. return false;
28. }
29. else{
30. father[fx] = fy;
31. return true;
32. }
33. }
34. int kruskal(){
35. sort(ee,ee+numedge,cmp);
36. for(int i = 1; i <= n; ++i)
37. father[i] = i;
38. int sum = 0;
39. for(int i = 0; i < numedge; ++i){
40. int lx = ee[i].lp;
41. int rx = ee[i].rp;
42. if(Union_Set(lx,rx)){
43. sum += ee[i].value;
44. }
45. }
46. return sum;
47. }
48. int main(){
49. //freopen(1.txt,r,stdin);
50. while(scanf(%d,&n) != EOF){
51. CLR(flag,0);
52. for(int i = 1; i <= n; ++i){
53. for(int j = 1; j <= n; ++j)
54. scanf(%d,&map[i][j]);
55. }
56. int m,x,y;
57. scanf(%d,&m);
58. while(m--){
59. scanf(%d%d,&x,&y);
60. flag[x][y] = 1;
61. }
62. numedge = 0;
63. for(int i = 1; i < n; ++i){
64. for(int j = i + 1; j <= n; ++j){
65. if(flag[i][j]){
66. ee[numedge].lp = i;
67. ee[numedge].rp = j;
68. ee[numedge].value = 0;
69. numedge++;
70. }
71. else{
72. ee[numedge].lp = i;
73. ee[numedge].rp = j;
74. ee[numedge].value = map[i][j];
75. numedge++;
76. }
77. }
78. }
79. int ans = kruskal();
80. printf(%d ,ans);
81. }
82. return 0;
83. }