记录编号	9600	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	1.136 s
提交时间	2009-04-06 17:31:04	内存使用	51.91 MiB

/* 
 * Problem: 通信线路
 * Author: Guo Jiabao
 * Time: 2009.4.6 17：32
 * State: Solved
 * Memo: 最小生成树 Prim
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1502,INF=0x7FFFFFFF;
using namespace std;
struct edge
{
	edge *next;
	int t,v;
}ES[MAXN*MAXN*2];
int N,Ans,EC=-1;
edge *V[MAXN];
int Mst[MAXN];
bool vis[MAXN];
inline void addedge(int a,int b,int v)
{
	ES[++EC].next=V[a];
	ES[EC].t=b;ES[EC].v=v;
	V[a]=&ES[EC];
}
void init()
{
	int i,j,c;
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
		{
			scanf("%d",&c);
			if (c!=-1)
				addedge(i,j,c);
		}
	}
}
void Prim()
{
	int i,j,Mini;
	for (i=1;i<=N;i++)
	{
		Mst[i]=INF;
		vis[i]=false;
	}
	for (Mst[i=1]=0;;)
	{
		vis[i]=true;
		for (edge *k=V[i];k;k=k->next)
		{
			if (!vis[k->t] && k->v < Mst[k->t])
				Mst[k->t]=k->v;
		}
		Mini=INF;i=-1;
		for (j=1;j<=N;j++)
		{
			if (!vis[j] && Mst[j]<Mini)
			{
				Mini=Mst[j];
				i=j;
			}
		}
		if (i==-1)
			break;
	}
}
void print()
{
	Ans=0;
	for (int i=1;i<=N;i++)
		Ans+=Mst[i];
	printf("%d\n",Ans);
}
int main()
{
	init();
	Prim();
	print();
	return 0;
}