758
hdu 4750 Count The Pairs 最小生成樹
比賽時候水了，一直打算算出22直接的關係數，然後又要考慮圖不連通情況等等，搞了半天還沒搞定。
其實隻要一層一層慢慢加就可以了，最後結果離線或者在線處理一下均可以。
因為最長路的最小值就相當於最小值一個一個添加
貼一下第一個AC隊的代碼，思路很清晰：
#include <cstdio>
#include<iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
struct edge
{
int x,y,len;
};
inline bool operator <(const edge &a,const edge &b)
{
return(a.len<b.len);
}
edge e[500010];
int f[10010],s[10010],a[10010];
ll sum[10010];
int find(int x)
{
if (x!=f[x])
f[x]=find(f[x]);
return(f[x]);
}
int main()
{
int n,m;
while (scanf("%d%d",&n,&m)==2)
{
for (int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[i].x=x+1,e[i].y=y+1,e[i].len=z;
}
sort(e+1,e+m+1);
for (int i=1;i<=n;i++)
{
f[i]=i;
s[i]=1;
}
int tot=0;
for (int i=1;i<=m;i++)
{
int x=find(e[i].x),y=find(e[i].y);
if (x==y)
continue;
a[++tot]=e[i].len;
sum[tot]=ll(s[x])*s[y];
f[x]=y;
s[y]+=s[x];
}
for (int i=1;i<=tot;i++)//求和
sum[i]+=sum[i-1];
int Q;
scanf("%d",&Q);
while (Q--)
{
int x;
scanf("%d",&x);
int id=lower_bound(a+1,a+tot+1,x)-a;
printf("%lld\n",(sum[tot]-sum[id-1])*2);
}
}
return(0);
}
最後更新：2017-04-03 15:21:46