记录编号	153750	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 数字梯形	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2015-03-19 07:50:07	内存使用	0.42 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=1e9;
int temp[21][45]={0},zz=0,zhi[21][45]={0};

int i,p,zj1,zj2,zj3,n,m,ans1,ans2,ans3,ST,SD;
int to[4500]={0},ne[4500]={0},head[1700]={0},w[4500]={0},r[4500]={0},sj=1;
inline void addedge(int u,int v,int W)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=W;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj,w[sj]=-W;
}

int que[1700]={0},qhead=1,qtail=0;bool flag[1700]={0};
inline void PUSH(int x)
{flag[x]=1,que[0]++;if(++qtail==1700)qtail=1;que[qtail]=x;}
inline int GET()
{int x=que[qhead];que[0]--,flag[x]=0;if(++qhead==1700)qhead=1;return x;}


int dis[1710]={0},pres[1710]={0},pre[1700]={0};
void init()
{
	scanf("%d%d",&n,&m);zj1=n;
	for(i=1;i<=m;i++,zj1++)for(p=1;p<=zj1;p++)
	scanf("%d",&zhi[i][p]),temp[i][p]=++zz;
	zj1=n;
	for(i=1;i<m;i++,zj1++)for(p=1;p<=zj1;p++)
	{
		addedge(temp[i][p],temp[i+1][p],zhi[i][p]);
		addedge(temp[i][p],temp[i+1][p+1],zhi[i][p]);
	}
	SD=zz+1;
	for(p=1;p<=zj1;p++)addedge(temp[i][p],SD,zhi[i][p]);
	for(i=1;i<=n;i++)
	{
		PUSH(i);
		for(p=1;p<=SD;p++)dis[p]=-INF;dis[i]=0;
		while(que[0])
		for(zj1=GET(),p=head[zj1];p;p=ne[p])
		if(to[p]>zj1&&dis[to[p]]<dis[zj1]+w[p])
		{
			
			dis[to[p]]=dis[zj1]+w[p];
			if(!flag[to[p]])PUSH(to[p]);
		}
		ans3+=dis[SD];
	}
}

inline bool spfa()
{
	for(i=1;i<=ST;i++)dis[i]=-INF;
	dis[ST]=0;PUSH(ST);
	while(que[0])
	{
		zj1=GET();
		for(i=head[zj1];i;i=ne[i])
		if(r[i]&&(dis[to[i]]<(zj2=dis[zj1]+w[i])))
		{
			dis[to[i]]=zj2,pre[to[i]]=zj1,pres[to[i]]=i;
			if(!flag[to[i]])PUSH(to[i]);
		}
	}
	if(dis[SD]==-INF)return 0;
	return 1;
}
 
inline int work()
{
	for(zj1=SD;zj1!=ST;zj1=pre[zj1])
	r[pres[zj1]]--,r[pres[zj1]^1]++;
	return dis[SD];
}

void Make()
{
	ST=SD+1;
	for(i=1;i<=n;i++)addedge(ST,temp[1][i],0);
	for(i=2;i<=sj;i+=2)r[i]=1;
	for(i=head[SD];i;i=ne[i])r[i^1]=INF;
	while(spfa())ans2+=work();
}

void End_()
{
	sj=1;memset(head,0,sizeof(head));zj1=n;
	for(i=1;i<m;i++,zj1++)for(p=1;p<=zj1;p++)
	{
		addedge(temp[i][p],temp[i][p]+zz,0);r[sj]=0;
		addedge(temp[i][p]+zz,temp[i+1][p],zhi[i][p]);r[sj]=0;
		addedge(temp[i][p]+zz,temp[i+1][p+1],zhi[i][p]);r[sj]=0;
	}
	SD=zz*2+1;ST=SD+1;
	for(p=1;p<=zj1;p++)
	{
		addedge(temp[i][p],temp[i][p]+zz,0),r[sj]=0;
		addedge(temp[i][p]+zz,SD,zhi[i][p]),r[sj]=0;
	}
	for(i=1;i<=n;i++)
	addedge(ST,temp[1][i],0),r[sj]=0;
	for(i=2;i<=sj;i+=2)r[i]=1;
	while(spfa())ans1+=work();
}
int main()
{
	freopen("digit.in","r",stdin);
	freopen("digit.out","w",stdout);
	init();
	Make();
	End_();
	printf("%d\n",ans1);
	printf("%d\n",ans2);
	printf("%d\n",ans3);
	return 0;
}