|
|
1  /**//*
2 3
31 2 1 0
41 3 2 0
52 3 4 0
63
71 2 1 0
81 3 2 0
92 3 4 1
103
111 2 1 0
121 3 2 1
132 3 4 1
140
15
16应该是一道最小生成树问题，找出N个点生成的最小树。把其中已经有道路连接的两个城市距离设为0
17 */
18 #include "cstdio"
19#include "map"
20#include "iostream"
21#include "cstring"
22#include "algorithm"
23#include "vector"
24#include "queue"
25
26using namespace std;
27
28typedef long long LL;
29typedef __int64 I64;
30typedef unsigned int uint;
31struct info
32 {
33 int i;
34 int j;
35 int cost;
36 bool operator < (const info &a) const
37  {
38 return a.cost < cost;
39 }
40};
41typedef struct info Point;
42const int inf = 0x7ffffff;
43const int Maxl = 105;
44int father[Maxl];
45
46int findx(int x);
47void merge(int x, int y);
48bool is_inc(Point p); //判断P节点指向的两个节点是否已经联通
49
50int main(void)
51{
52 Point pt; //确切地说，应该定义为Edge
53 priority_queue<Point> my_que;
54 uint n;
55 while (scanf("%d", &n) == 1 && n)
56 {
57 uint k = n * (n-1) / 2, m, i, j, cost, flag;
58 //初始化并查集数组
59 for (i = 0; i < Maxl; i++)
60 {
61 father[i] = i;
62 }
63 while(k--)
64 {
65 scanf("%d %d %d %d", &i, &j, &cost, &flag);
66 if (flag == 1)
67 {
68 pt.cost = 0;
69 }
70 else
71 pt.cost = cost;
72 pt.i = i;
73 pt.j = j;
74 my_que.push(pt);
75 }
76 i = 1;
77 uint sum = 0;
78 //下面这段循环取出前面n-1个最小的边
79 while(!my_que.empty())
80 {
81 if (!is_inc(my_que.top()))
82 {
83 sum += my_que.top().cost;
84 merge(my_que.top().i, my_que.top().j);
85 }
86 my_que.pop();
87 }
88 printf("%d\n",sum);
89 }
90 return 0;
91}
92
93int findx(int x)
94{
95 int r = x;
96 while (r != father[r])
97 {
98 r = father[r];
99 }
100 return r;
101
102}
103
104void merge(int x, int y)
105{
106 int xx = findx(x);
107 int yy = findx(y);
108 father[yy] = xx;
109}
110
111bool is_inc(Point p)
112{
113 int xx = findx(p.i);
114 int yy = findx(p.j);
115 if (xx == yy)
116 {
117 return true;
118 }
119 else
120 return false;
121}
|