2016 NEERC, Moscow Subregional Contest K. Knights of the Old Republic



题意：有一张图，第i个点被占领需要ai个兵，而每个兵传送至该点需要bi的费用。占领第i条边需要其两端点的兵数之和大等于ci。对于已占领的点或边可以免费通行。因此兵达到一个点的手段有传送和沿路走。图上的兵可以在已占领的点、边随意调度。

求占领所有点的最小花费。

思路：将边按ci进行升序排列，对于每条边两端点所在的连通块进行合并，合并细节见代码。这里有一点值得思考：当你想打通当前这条边时，由于排了序，你总可以默认之前那些ci小的边已打通（因为兵可以调度）。因此，我们需要用并查集维护连通块，以及每个连通块中最小的传送单价，最大的单点兵需求量，来更新花费。

#include<iostream>

#include<cstdio>

#include<algorithm>

#define fi first

#define se second

using namespace std;

typedef long long ll;

typedef pair<ll,pair<int,int> > P;

const int maxn=3e5+10;

P edge[maxn];

int fa[maxn];

ll a[maxn],b[maxn],cost[maxn];

void init(int n)

{

  for (int i=1;i<=n;++i)

  {

  	fa[i]=i;

	cost[i]=a[i]*b[i];

  }

}

int find(int x)

{

  return fa[x]==x?x:fa[x]=find(fa[x]);

}

void unio(int x,int y,ll c)

{

  int fx=find(x),fy=find(y);

  if (fx==fy)

  	return;

  fa[fx]=fy;

  a[fy]=max(c,max(a[fy],a[fx]));

  b[fy]=min(b[fy],b[fx]);

  cost[fy]=min(cost[fy]+cost[fx],a[fy]*b[fy]);

}

int main()

{

  int n,m;

  scanf("%d%d",&n,&m);

  for (int i=1;i<=n;++i)

  	scanf("%lld%lld",&a[i],&b[i]);

  for (int i=0;i<m;++i)

  	scanf("%d%d%lld",&edge[i].se.fi,&edge[i].se.se,&edge[i].fi);

  sort(edge,edge+m);

  init(n);

  for (int i=0;i<m;++i)

  {

  	int u=edge[i].se.fi,v=edge[i].se.se,c=edge[i].fi;

  	unio(u,v,c);

  }

  ll ans=0;

  for (int i=1;i<=n;++i)

	if (fa[i]==i)

	  ans+=cost[i];

  printf("%lld",ans);

  return 0;

}