The 2020 ICPC Asia Taipei-Hsinchu Site Programming Contest H. Optimization for UltraNet （二分+最小生成树+算贡献）
原题链接
题意：
求生成树，使得最小边权最大，在此基础上任意两点路径上的最短边权值之和最小。求任意两点路径上的最短边权值之和。
思路：
最小边权最大，很容易可以想到二分。
二分最小边权的位置，每次检查是否能够构成生成树。
对于答案的计算，考虑每个边的贡献。将所选边从小到大排序，如果当前边能够连接两个连通块，当前边的贡献就是w * siz[fu] * siz[fv]。
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e6+7; struct node{ ll u,v,w; }edge[maxn]; bool cmp(node a,node b){ return a.w<b.w; } bool cmp1(node a,node b){ return a.w>b.w; } int n,m,root[maxn]; int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } int h[maxn],idx; struct node1{ ll e,ne,w; }edge1[maxn]; void add1(int u,int v,int w){ edge1[idx]={v,h[u],w};h[u]=idx++; } bool check(int mid){ if(m-mid+1<n-1) return 0; int cnt=0; rep(i,1,n) root[i]=i; rep(i,mid,m){ int u=edge[i].u,v=edge[i].v,w=edge[i].w; int fu=Find(u),fv=Find(v); if(fu!=fv){ root[fu]=fv; cnt++; //add1(u,v,w);add1(v,u,w); } if(cnt==n-1) break; } if(cnt==n-1) return 1; return 0; } ll siz[maxn]; void solve(){ n=read,m=read; //rep(i,1,n) root[i]=i; rep(i,1,m){ ll u=read,v=read,w=read; edge[i]={u,v,w}; } sort(edge+1,edge+1+m,cmp); int l=1,r=m,ans;//枚举最短边所在的位置 //最短边最长 while(l<=r){ int mid=(l+r)/2; if(check(mid)){//还可以更长 ans=mid;l=mid+1; } else r=mid-1; } memset(h,-1,sizeof h); int cnt=0; rep(i,1,n) root[i]=i; rep(i,ans,m){ ll u=edge[i].u,v=edge[i].v,w=edge[i].w; int fu=Find(u),fv=Find(v); if(fu!=fv){ root[fu]=fv; cnt++; // add1(u,v,w);add1(v,u,w); edge[cnt]={u,v,w}; } if(cnt==n-1) break; } sort(edge+1,edge+1+cnt,cmp1); ll res=0; rep(i,1,n) root[i]=i,siz[i]=1; rep(i,1,cnt){ ll u=edge[i].u,v=edge[i].v,w=edge[i].w; int fu=Find(u),fv=Find(v); if(fu!=fv){ root[fu]=fv; res=res+w*siz[fu]*siz[fv]; siz[fv]+=siz[fu]; } } printf("%lld\n",res); } int main(){ int T=1; while(T--) solve(); return 0; }
