点击打开链接
两种解法
一：
二分最长边 求最大生成树
#include <bits/stdc++.h> using namespace std; #define ll long long struct node { int u; int v; ll w; }; node edge[200010]; ll len[200010]; ll ans; int f[100010]; int n,m; int cmp(node n1,node n2) { return n1.w>n2.w; } int getf(int p) { if(f[p]==p) return p; else { f[p]=getf(f[p]); return f[p]; } } int unite(int u,int v) { int fu,fv; fu=getf(u); fv=getf(v); if(fu!=fv) { f[fv]=fu; return 1; } else { return 0; } } ll judge(ll lim) { ll sum; int i,p,cnt; for(i=1;i<=n;i++) { f[i]=i; } sum=0,cnt=0,p=0; for(i=1;i<=m;i++) { if(edge[i].w<=lim) { p=i; break; } } for(i=p;i<=m;i++) { if(unite(edge[i].u,edge[i].v)) { sum+=edge[i].w; cnt++; } if(cnt==n-1) break; } if(cnt==n-1) return sum; else return -1; } void binsearch() { ll t; int i,j,l,r,mid; j=0; for(i=1;i<=m;i++) { if(edge[i].w!=len[j]) { j++; len[j]=edge[i].w; } } l=1,r=j,ans=0; while(l<=r) { mid=(l+r)/2; t=judge(len[mid]); if(t!=-1) { ans=t; l=mid+1; } else { r=mid-1; } } return; } int main() { int i,j; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=m;i++) { scanf("%d%d%lld",&edge[i].u,&edge[i].v,&edge[i].w); } sort(edge+1,edge+m+1,cmp); binsearch(); printf("%lld\n",ans); } return 0; }
二：
题意其实是先保证最大边最小 其次总和最大 就是说只要保证能形成(n-1)条边的连通图 树中最大边越小越好
于是先考虑形成一个最小生成树 再凑最大生成树 这样可以确定所谓的"最小的最大边"
这样考虑是因为生成树不管最大还是最小 都是生成一个(n-1)条边的连通图 而在找到(n-1)条边形成这颗最小生成树后 最后一条放入生成树中的边的边长即为"最小的最大边"的长
注意是边长 因为等长的边还可能有其他的边 这些边在构成最大生成树时可能会用到 这里WA了几发才发现..
再用所有不超过这个长度限定的边构成最大生成树即可
#include <stdio.h> #include <algorithm> using namespace std; struct node { int u; int v; long long w; }; struct node edge[200001]; int f[100001]; int n,m; int cmp(node n1,node n2) { return n1.w<n2.w; } int unite(int u,int v); int getf(int p); int main() { long long sum; int i,j,cnt,p; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=m;i++) { scanf("%d%d%lld",&edge[i].u,&edge[i].v,&edge[i].w); } sort(edge+1,edge+m+1,cmp); for(i=1;i<=n;i++) { f[i]=i; } cnt=0; for(i=1;i<=m;i++) { if(unite(edge[i].u,edge[i].v)) { cnt++; } if(cnt==n-1) { p=i; break; } } for(i=p+1;i<=m;i++) { if(edge[i].w==edge[p].w) p=i; else break; } for(i=1;i<=n;i++) { f[i]=i; } cnt=0,sum=0; for(i=p;i>=1;i--) { if(unite(edge[i].u,edge[i].v)) { cnt++; sum+=edge[i].w; } if(cnt==n-1) { break; } } printf("%lld\n",sum); } return 0; } int unite(int u,int v) { int fu,fv; fu=getf(u); fv=getf(v); if(fu!=fv) { f[fv]=fu; return 1; } else return 0; } int getf(int p) { if(f[p]==p) return p; else { f[p]=getf(f[p]); return f[p]; } }
