记录编号	380530	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.593 s
提交时间	2017-03-09 16:58:02	内存使用	27.82 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,all=1,sum,A;
vector<int> CT[1600];
bool Pan,pana,panb[1600];
int panc[1600];
struct Ms
{
	int a,b;
	int PR;
	Ms(){a=0;b=0;PR=0;}
	bool operator <(const Ms P)const 
	{
		return PR<P.PR;
	}
}ms[1501*1600];
inline bool pan(int c,int m,int C,bool d)
{
	if(c==m){pana=0;return 0;}
	if(CT[c].empty()&&d){Pan=1;return 1;}
	else
	{
		for(int i=0;i<CT[c].size();i++)
		{
			if(panb[CT[c][i]])continue;
			panb[CT[c][i]]=1;
			if(i+1==CT[c].size())pan(CT[c][i],m,C+1,1);
			else pan(CT[c][i],m,C+1,0);
			panb[CT[c][i]]=0;
			if(Pan==1)return 1;
			if(pana==0)return 0;
		}
		if(C==1)return 1;
	}
}
bool pp()
{
	for(int i=1;i<=n;i++)
	{
		if(panc[i]!=A)return 0;
	}
	return 1;
}
int main()
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int a;
			scanf("%d",&a);
			ms[all].a=i;ms[all].b=j;ms[all].PR=a;
			all++;
		}
	}
	sort(ms,ms+all);
	for(int i=1;i<=all;i++)
	{
		int a=ms[i].a,b=ms[i].b;
		if(ms[i].PR==-1||ms[i].a==0||ms[i].b==0)continue;
		Pan=0;pana=1;panb[a]=1;
		if(pan(ms[i].a,ms[i].b,1,1))
		{
			sum+=ms[i].PR;A++;
			CT[ms[i].a].push_back(ms[i].b);
			CT[ms[i].b].push_back(ms[i].a);
			panc[a]+=b;panc[b]+=a;
		}
		panb[ms[i].a]=0;
		if(A+1==n){printf("%d",sum);return 0;}
	}
	printf("%d",sum);
	return 0;
}