蓝桥杯城市建设

思路：

将河看做一个额外的点，将修码头看成是在相应地点和河之间连边，然后考虑是否修码头两种情况用最小生成树求解。需要注意的是如果边的权值是负数，那么即是已经连通，也要加这条边。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 10005;
 4 const int MAXM = 100005;
 5 const int INF = 0x3f3f3f3f;
 6 struct node
 7 {
 8     int x, y, c;
 9 };
10 node a[MAXN + MAXM];
11 int par[MAXN];
12 void init(int n)
13 {
14     for (int i = 1; i <= n; i++) par[i] = i;
15 }
16 int find(int x)
17 {
18     if (x == par[x]) return x;
19     return par[x] = find(par[x]);
20 }
21 bool same(int x, int y)
22 {
23     return find(x) == find(y);
24 }
25 void uni(int x, int y)
26 {
27     x = find(x); y = find(y);
28     if (x != y) par[x] = y;
29 }
30 bool cmp(node & a, node & b)
31 {
32     return a.c < b.c;
33 }
34 int kru(int n, int m)
35 {
36     init(n);
37     sort(a + 1, a + m + 1, cmp);
38     int cost = 0, cnt = n;
39     for (int i = 1; i <= m; i++)
40     {
41         if (!same(a[i].x, a[i].y))
42         {
43             uni(a[i].x, a[i].y);
44             cnt--;
45             cost += a[i].c;
46         }
47         else if (a[i].c < 0) cost += a[i].c;
48     }
49     return cnt == 1 ? cost : INF;
50 }
51 int main()
52 {
53     int n, m, w;
54     cin >> n >> m;
55     for (int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y >> a[i].c;
56     int cost = kru(n, m);
57     int now = m + 1;
58     for (int i = 1; i <= n; i++)
59     {
60         cin >> w;
61         if (w == -1) continue;
62         a[now].x = i; a[now].y = n + 1; a[now++].c = w;
63     }
64     int cost1 = kru(n + 1, now - 1);
65     cout << min(cost, cost1) << endl;
66     return 0;
67 }

蓝桥杯 城市建设

蓝桥杯城市建设