3.6 最小生成树的扩展应用
3.6.1 1146. 新的开始
代码：
#include<bits/stdc++.h> using namespace std; const int N=310,M=100010; int n,m; int p[N]; int money[N]; struct Edge{ int a,b,w; }edges[M]; bool cmp(Edge a,Edge b) { return a.w<b.w; } int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int kruskal() { sort(edges,edges+m,cmp); for(int i=1;i<=n+1;i++) p[i]=i; int res=0; for(int i=0;i<m;i++) { int a=edges[i].a,b=edges[i].b,w=edges[i].w; a=findP(a),b=findP(b); if(a!=b) { p[a]=b; res+=w; } } return res; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>money[i]; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int w; cin>>w; if(i<j) { edges[m].a=i,edges[m].b=j,edges[m].w=w; m++; } } } for(int i=1;i<=n;i++) { edges[m].a=n+1,edges[m].b=i,edges[m].w=money[i]; m++; } cout<<kruskal(); return 0; }
3.6.2 1145. 北极通讯网络
代码：
#include using namespace std; typedef pair PII; const int N=510,M=250010; int n,m,k; int p[N]; PII mp[N]; struct Edge{ int a,b; double w; }edges[M]; bool cmp(Edge a,Edge b) { return a.w } int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int check() { set st; for(int i=1;i<=n;i++) { st.insert(findP(i)); } return st.size(); } double kruskal() { sort(edges,edges+m,cmp); for(int i=1;i<=n;i++) p[i]=i; double res=0; for(int i=0;i { int a=edges[i].a,b=edges[i].b; double w=edges[i].w; a=findP(a),b=findP(b); if(a!=b) { p[a]=b; res=w; } if(check()<=k) break; } return res; } int main() { cin>>n>>k; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; mp[i]=make_pair(x,y); } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { double x1=mp[i].first,y1=mp[i].second,x2=mp[j].first,y2=mp[j].second; double w=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); edges[m].a=i,edges[m].b=j,edges[m].w=w; m++; } } printf("%.2f",kruskal()); return 0; } 1
3.6.3 346. 走廊泼水节
代码：
#include using namespace std; typedef pair PII; const int N=6010,M=6010; int T,n,m; int p[N],sz[N]; map mp; struct Edge{ int a,b,w; }edges[M]; bool cmp(Edge a,Edge b) { return a.w } int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int kruskal() { sort(edges,edges+m,cmp); for(int i=1;i<=n;i++) { p[i]=i; sz[i]=1; } int res=0; for(int i=0;i { int a=edges[i].a,b=edges[i].b,w=edges[i].w; a=findP(a),b=findP(b); if(a!=b) { res+=(sz[a]*sz[b]-1)*(w+1); sz[b]+=sz[a]; p[a]=b; } } return res; } int main() { cin>>T; while(T--) { cin>>n; for(int i=0;i { int a,b,w; cin>>a>>b>>w; edges[i].a=a,edges[i].b=b,edges[i].w=w; } m=n-1; cout< } return 0; }
3.6.4 1148. 秘密的牛奶运输
代码：
#include using namespace std; typedef long long LL; const int N=510,M=10010; const LL INF=1e18; int n,m; int p[N]; int dis1[N][N],dis2[N][N]; int h[N],e[N*2],w[N*2],ne[N*2],idx; struct Edge{ int a,b,w; bool type; }edges[M]; bool cmp(Edge a,Edge b) { return a.w } void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } void dfs(int u,int fa,int maxd1,int maxd2,int d1[],int d2[]) { d1[u]=maxd1,d2[u]=maxd2; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(j!=fa) { int td1=maxd1,td2=maxd2; if(w[i]>td1) td2=td1,td1=w[i]; else if(w[i]td2) td2=w[i]; dfs(j,u,td1,td2,d1,d2); } } } LL kruskal() { sort(edges,edges+m,cmp); for(int i=1;i<=n;i++) p[i]=i; LL res=0; for(int i=0;i { int a=edges[i].a,b=edges[i].b,w=edges[i].w; int pa=findP(a),pb=findP(b); if(pa!=pb) { p[pa]=pb; add(a,b,w),add(b,a,w); edges[i].type=true; res+=w; } } return res; } int main() { memset(h,-1,sizeof h); cin>>n>>m; for(int i=0;i { cin>>edges[i].a>>edges[i].b>>edges[i].w; } LL sum=kruskal(); for(int i=1;i<=n;i++) dfs(i,-1,-1e9,-1e9,dis1[i],dis2[i]); LL res=INF; for(int i=0;i { if(!edges[i].type) { int a=edges[i].a,b=edges[i].b,w=edges[i].w; if(w>dis1[a][b]) { res=min(res,sum+w-dis1[a][b]); } else if(w>dis2[a][b]) { res=min(res,sum+w-dis2[a][b]); } } } cout< return 0; }
