Week6：种田——并查集
题目描述
东东在老家农村无聊，想种田。农田有 n 块，编号从 1~n。种田要灌氵
众所周知东东是一个魔法师，他可以消耗一定的 MP 在一块田上施展魔法，使得黄河之水天上来。他也可以消耗一定的 MP 在两块田的渠上建立传送门，使得这块田引用那块有水的田的水。 (1<=n<=3e2)
黄河之水天上来的消耗是 Wi，i 是农田编号 (1<=Wi<=1e5)
建立传送门的消耗是 Pij，i、j 是农田编号 (1<= Pij <=1e5, Pij = Pji, Pii =0)
东东为所有的田灌水的最小消耗。
输入格式
第1行：一个数n
第2行到第n+1行：数wi
第n+2行到第2n+1行：矩阵即pij矩阵
输出格式
东东最小消耗的MP值
输入示例
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
输出示例
9
解题思路
要求灌满所有的田，还要最小消耗，那么并查集就很适合这道题了。
把所有的边加入到一个数组中去，然后根据权值从小到大排序。
然后执行并查集就行了。
判断终点是所有的点都被边连起来了。
但是这里题目中说明了，不一定非要从某个点一直饮水出来，也可以在某个点重新灌水灌出一个起点。
那么这里就可以采取bfs时可以采取的多起点思路——在初始化时，设置一个超级源点，所有点到这个超级源点的距离就是这个点的灌水代价。
然后对着这个超级源点跑并查集即可。
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>using namespace std;
int father[305];struct Node
{int u, v, w;Node(int _u, int _v, int _w){u = _u; v = _v; w = _w;}
};vector<Node>node;int n;int findfather(int x)
{if (father[x] == x) return x;else return father[x] = findfather(father[x]);
}bool cmp(Node a, Node b)
{if (a.w != b.w) return a.w < b.w;else if (a.u != b.u) return a.u < b.u;else return a.v < b.v;
}int main()
{cin >> n;for (int i = 0; i <= n; i++) father[i] = i;//同时初始化超级源点for (int i = 1, a; i <= n; i++){cin >> a;node.push_back(Node(0, i, a));node.push_back(Node(i, 0, a));}for (int i = 1, a; i <= n; i++){for (int j = 1; j <= n; j++){cin >> a;if (i == j) continue;node.push_back(Node(i, j, a));//node.push_back(Node(j, i, a));}}sort(node.begin(), node.end(), cmp);int cnt = 0;int ans = 0;for (int i = 0; i < node.size(); i++){if (cnt == n) break;int u = node[i].u;int v = node[i].v;int faA = findfather(u), faB = findfather(v);if (faA != faB){father[faA] = faB;ans += node[i].w;cnt++;}}cout << ans;
}
发布评论