题目大意：给定一张无向图，每个点有边权，给每个联通块大小一个喜爱度，求一个最小的区间，使保留这个区间内的所有边权的边时喜爱度之和最大
n<=1000,m<=5000
脑残没法治系列……
如果暴力枚举区间并每次计算喜爱度，时间复杂度为O(nm^2)，超时
固定一个左端点，将右端点右移，每次用并查集加边并维护喜爱度之和，时间复杂度O(m^2)
然后这题就做完了= =
#include
#include
#include
#include
#define M 1010 using namespace std; struct abcd{ int x,y,f; friend istream& operator >> (istream &_,abcd &a) { scanf("%d%d%d",&a.x,&a.y,&a.f); return _; } bool operator < (const abcd &a) const { return f
size[y]) swap(x,y); sum-=w[size[x]]; sum-=w[size[y]]; fa[x]=y;size[y]+=size[x]; sum+=w[size[y]]; } } int main() { using namespace Union_Find_Set; int i,j; cin>>n>>m>>k; for(i=1;i<=n;i++) scanf("%d",&w[i]); for(i=1;i<=m;i++) cin>>edges[i]; sort(edges+1,edges+m+1); for(i=1;i<=m;i++) if(i==1||edges[i].f!=edges[i-1].f) { sum=(long long)n*w[1]; memset(fa,0,sizeof fa); for(j=i;j<=m;j++) { Union(edges[j].x,edges[j].y); if(j==m||edges[j].f!=edges[j+1].f) if(sum>=k) { ans=min(ans,edges[j].f-edges[i].f); break; } } } if(ans==2147483647) cout<<"T_T"<