题目描述
栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。
C市中有n个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。
栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。
市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。
输入
输入的第一行包含两个整数n, m，分别表示C市中重要地点的个数和可以建设的道路条数。所有地点从1到n依次编号。
接下来m行，每行三个整数a, b, c，表示可以建设一条从地点a到地点b的道路，花费为c。若c为正，表示建设是花钱的，如果c为负，则表示建设了道路后还可以赚钱（比如建设收费道路）。
接下来一行，包含n个整数w_1, w_2, …, w_n。如果w_i为正数，则表示在地点i建设码头的花费，如果w_i为-1，则表示地点i无法建设码头。
输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。
输出
输出一行，包含一个整数，表示使得所有地点通过新修道路或者码头连接的最小花费。如果满足条件的情况下还能赚钱，那么你应该输出一个负数。
样例输入
5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1
样例输出
9
思路
最小生成树变种题，除去码头建设就是完全的Kruskra法求最小生成树了。
我们可以引入一个河流点为0点来将建设码头也当做边加入边集中求最小生成树。
码头建设要考虑两个问题:
1.建设码头能不能实现全连通，因为，题目没有说仅靠道路建设就能实现全连通，所以需要判断一下。
2.建设码头和不建设码头到底谁更赚，因为建设码头引入了0点所以最小生成树代价是包括0点的(也就是有可能会出现没有用到码头连通城市但建了一座码头的情况)
考虑完即可。(还有一个注意点就是，道路的所有的负边都要加入，因为是铁赚的)
if(不建码头连通数!=n) cout<<Kruskra(建设码头);
else min(Kruskra(不建设码头),Kruskra(建设码头));
代码:(耗时:281ms)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node{
int from;
int to;
int cost;
}a[200010];
int f[10010],r[10010],cnt = 0;
bool cmp(const Node&s1,const Node&s2){
return s1.cost<s2.cost;
}
int find_father(int x){return x==f[x]?x:f[x] = find_father(f[x]);}
long long Kfunc(int m,int n){
long long cost = 0;
for(int i = 0;i<=n;i++){f[i] = i;}
sort(a,a+m,cmp);
for(int i = 0;i<m;i++){
int fx = find_father(a[i].from);
int fy = find_father(a[i].to);
if(fx!=fy || a[i].cost<0){//负边铁赚，所以要加入
cost+=a[i].cost;
if(fx!=fy){
f[fx] = fy;
cnt++;
}
}
}
return cost;
}
int main(){
int n,m,flag = 0;
long long cost1 = 0,cost2 = 0;
scanf("%d%d",&n,&m);
for(int i = 0;i<m;i++)
scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].cost);
for(int i = 1;i<=n;i++)
scanf("%d",&r[i]);
cost1 = Kfunc(m,n);
if(cnt==n-1) flag = 1;
for(int i = 1;i<=n;i++){
if(r[i]!=-1){
a[m].from = 0;
a[m].to = i;
a[m].cost = r[i];
m++;
}
}
cost2 = Kfunc(m,n);
if(flag) cout<<min(cost1,cost2);
else cout<<cost2;
return 0;
}
网友评论