记录编号	16064	评测结果	AAAAAAAAAA
题目名称	429.城市规划	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.173 s
提交时间	2010-04-19 14:03:50	内存使用	1.19 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>

using namespace std;
const int oo=2000000000;
const int maxn=200+1;
int f[maxn][maxn],n;
void init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	{
		scanf("%d",&f[i][j]);
		if (f[i][j]<=0)  f[i][j]=oo;
	}
}

bool y[maxn];
int p[maxn][maxn];
int come[maxn];
int path[maxn][maxn];
int d[maxn][maxn],q[10*maxn];
int lo[maxn][maxn];
int lon[maxn][maxn];
int qt,qw,ans;
bool inq[maxn];

void spfa(int S)
{
	qw=-1;qt=0;
	for (int i=1;i<=n;i++)
	{
		if (i!=S) d[S][i]=oo;
		else d[S][i]=0;
	}
	q[++qw]=S;inq[S]=true;
	while (qt<=qw)
	{
		int u=q[qt];
		for (int v=1;v<=n;v++)
		if (f[u][v]<oo)
		{
			if (d[S][v]>d[S][u]+f[u][v] || 
				(d[S][v]==d[S][u]+f[u][v] && (lo[S][v]>=lo[S][u]+(1-path[u][v])*f[u][v] 
				|| lon[S][v]>lon[S][u]+(1-path[u][v]) )  )   )
			{
				d[S][v]=d[S][u]+f[u][v];
				lo[S][v]=lo[S][u]+(1-path[u][v])*f[u][v];
				lon[S][v]=lon[S][u]+(1-path[u][v]);
				p[S][v]=u;
				if (!inq[v])
				{
					q[++qw]=v;
					inq[v]=true;
				}
			}
		}
		inq[q[qt++]]=false;
	}
	for (int i=1;i<=n;i++)
	{
		int now=i;
		while (p[S][now]!=0 && !path[p[S][now]][now])
		{
			path[p[S][now]][now]=1;
			path[now][p[S][now]]=1;
			ans+=f[p[S][now]][now];
		}
	}
}

int main()
{
	freopen("cityroad.in","r",stdin);
	freopen("cityroad.out","w",stdout);
	init();
	for (int i=1;i<=n;i++)
		spfa(i);
	printf("%d\n",ans);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<n;j++)
		{
			printf("%d ",path[i][j]);
		}
		printf("%d\n",path[i][n]);
	}
	return 0;
}