BZOJ 3454 家族 並查集
題目大意：給定一張無向圖，每個點有邊權，給每個聯通塊大小一個喜愛度，求一個最小的區間，使保留這個區間內的所有邊權的邊時喜愛度之和最大
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 fsize[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"<
