BZOJ 1601 [Usaco2008 Oct]灌水

题目大意

给你一个田地，每块田地要么建立一个水池要么从有水池的田地引水，这两件事情都需要一定费用，求最小费用使得所有田地都有水。

这道题看到联通基本就可以敲定是最小生成树了，但是死活没想到咋解决边权……整一个超级源点向每条边连边，就可以解决点权问题。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,inx,S=0,head[500],fa[500],tot,ans,cnt;
struct edge
{
	int from,to,val;
}e[1000000];
void addedge(int tx,int ty,int tz)
{
	e[++tot].to=ty,e[tot].from=tx,e[tot].val=tz;
	e[++tot].to=tx,e[tot].from=ty,e[tot].val=tz;
}
int unifind(int tx) {return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);}
void kruskal()
{
	for(int i=1;i<=tot;++i)
	{
		int tx=unifind(e[i].from),ty=unifind(e[i].to);
		if(tx!=ty)
		{
			++cnt;
			fa[tx]=ty;
			ans+=e[i].val;
			if(cnt==n) return;
		}
	}
}
bool cmp(edge tx,edge ty) {return tx.val<ty.val;}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<=n;++i) fa[i]=i;
	for(int i=1;i<=n;++i) scanf("%d",&inx),addedge(S,i,inx);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		{
			scanf("%d",&inx);
			addedge(i,j,inx);
		}
	sort(e+1,e+tot+1,cmp);
	kruskal();
	printf("%d\n",ans);
}