利用excel做填报网站/有没有可以代理推广的平台

$Description$

一张带权无向图$G(V,E)$
若一个大小为$i$的连通分量贡献为$a_i$
则一张图的价值即为所有连通分量大小的权值和

求切割掉权值在一定范围内的边后价值仍不小于给定的$K$，求该范围的最小极差

$n\le 10^3,m\le 5\times 10^3$

$Solution$

容易想到该范围必然是两个是两条边的权值，所以我们可以枚举边，复杂度$O(m^2)$，为了保证边是有序的，得先排序，复杂度$O(mlogm)$，接下来的瓶颈在于计算贡献

统计联通分块可以用并查集实现，对于联通块的大小，开一个$t_i$数组表示每个集合内元素个数即可实现$O(\alpha (n))$转移

总的时间复杂度是$O(m^2\alpha (n))$

$Code$

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;int n,m,K,jz[1001],ans=0x3f3f3f3f,f[1001],t[1001];
long long sum;
struct node{int from,to,hz;}e[5001];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}//路径压缩
inline bool cmp(node x,node y){return x.hz<y.hz;}
inline int read()
{int f=0,d=1;char c;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{n=read();m=read();K=read();for(register int i=1;i<=n;i++) jz[i]=read();for(register int i=1;i<=m;i++) e[i].from=read(),e[i].to=read(),e[i].hz=read();sort(e+1,e+1+m,cmp);for(register int i=1;i<=m;i++){for(register int j=1;j<=n;j++) f[j]=j,t[j]=1;sum=jz[1]*n;for(register int j=i;j<=m;j++){int x=find(e[j].from),y=find(e[j].to);if(x==y) continue;sum+=jz[t[x]+t[y]]-jz[t[x]]-jz[t[y]];if(x<y) f[y]=f[x],t[x]+=t[y];else f[x]=f[y],t[y]+=t[x];//按秩合并if(e[j].hz-e[i].hz>ans) break;//最优化剪枝if(e[j].hz!=e[j+1].hz&&sum>=K){ans=min(ans,e[j].hz-e[i].hz);break;}}}if(ans==0x3f3f3f3f) return puts("T_T")&0;printf("%d",ans);
}