[最小生成树] 蓝桥杯 城市建设

题意：

n个城市，m条边。额外的是，每个城市还可以建码头。

如果两个城市都有码头，则这两个城市可以互相到达。

求最小生成树。

思路：

对于码头，可以把所有码头都连到一个0点，，代价是建码头的费用。

这时候就跑两遍，一遍是有码头的情况，第二遍没有码头。

这样的话就一个问题，就是如果没有码头的话，道路会不会都联通。

然后还要注意，负数的道路是必须连的，这样费用更小！

代码：

#include"stdio.h"#include"algorithm"#include"string.h"#include"iostream"#include"queue"#include"map"#include"string"#define mod 1000000007using namespace std;struct node{int x,y,s;} edge[123456];int pre[12345];int cmp(node a,node b){return a.s<b.s;}int finde(int x){return x!=pre[x]?pre[x]=finde(pre[x]):x;}int main(){int n,m;while(scanf("%d%d",&n,&m)!=-1){for(int i=0; i<=n; i++) pre[i]=i;for(int i=0; i<m; i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].s);for(int i=m; i<n+m; i++){edge[i].x=0;edge[i].y=i-m+1;scanf("%d",&edge[i].s);if(edge[i].s==-1) edge[i].s=-19999;}sort(edge,edge+n+m,cmp);int ans=0,ans2=0;for(int i=0; i<n+m; i++){if(edge[i].s==-19999) continue;int f1=finde(edge[i].x);int f2=finde(edge[i].y);if(f1!=f2){ans+=edge[i].s;pre[f1]=f2;}else if(edge[i].s<0) ans+=edge[i].s;}for(int i=0; i<=n; i++) pre[i]=i;for(int i=0; i<n+m; i++){if(edge[i].x==0) continue;int f1=finde(edge[i].x);int f2=finde(edge[i].y);if(f1!=f2){ans2+=edge[i].s;pre[f1]=f2;}else if(edge[i].s<0) ans2+=edge[i].s;}int sum=0;for(int i=1;i<=n;i++) if(pre[i]==i) sum++;if(sum!=1) printf("%d\n",ans);else printf("%d\n",min(ans,ans2));}return 0;}

一个背包，几本书，所有喜欢的歌，