记录编号	157717	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 数字梯形	最终得分	100
用户昵称	vampire	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2015-04-09 21:19:32	内存使用	4.35 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int point[1500]={0},next[10000]={0},tot,n,m,map[50][50],l[1000000],dis[1500],pre[1500],num[30]={0},sum[30]={0};
bool f[1500];
struct S{
	int st,en,va,co;
}aa[10000];
inline void add(int i,int j,int x,int y)
{
	tot+=1;next[tot]=point[i];point[i]=tot;
	aa[tot].st=i;aa[tot].en=j;aa[tot].va=x;aa[tot].co=y;
	tot+=1;next[tot]=point[j];point[j]=tot;
	aa[tot].st=j;aa[tot].en=i;aa[tot].va=0;aa[tot].co=-y;
}
inline int SPFA(int x,int y)
{
	memset(f,1,sizeof(f));
	memset(dis,128,sizeof(dis));
	memset(pre,0,sizeof(pre));
	int i,j,u,h=1,t=1;
	dis[x]=0;l[h]=x,pre[x]=x;
	while(h<=t){
		u=l[h];f[u]=true;
		for(i=point[u];i;i=next[i]){
			if(aa[i].va>0&&dis[aa[i].en]<dis[u]+aa[i].co){
				dis[aa[i].en]=dis[u]+aa[i].co;
				pre[aa[i].en]=i;
				if(f[aa[i].en]){
					t+=1;
					f[aa[i].en]=false;
					l[t]=aa[i].en;
				}
			}
		}
		h+=1;
	}
	return dis[y]<0?0:dis[y];
} 
inline int ISAP(int x,int y)
{
	int i,minn=210000000;
	for(i=y;i!=x;i=aa[pre[i]].st){
		minn=min(minn,aa[pre[i]].va);
	}
	for(i=y;i!=x;i=aa[pre[i]].st){
		aa[pre[i]].va-=minn;
		aa[pre[i]^1].va+=minn;
	}
	return minn;
}
int main()
{
	freopen("digit.in","r",stdin);
	freopen("digit.out","w",stdout);
	int i,j,N,T,num1,num2,minn,ans;
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;++i)
	  for(j=1;j<=m+i-1;++j)
	    scanf("%d",&map[i][j]);	
	N=(m*2+n-1)*n/2;
	for(i=1;i<=n;++i) num[i]=num[i-1]+m+i-1,sum[i]=m+i-1;
    /*-----------work1-----------*/
    tot=1;T=N*2-m+2;
	for(i=1;i<=m;++i) add(1,i+1,1,0);
	for(i=1;i<=m;++i) {add(i+1,i+m+1,1,map[1][i]);add(i+1,i+m+2,1,map[1][i]);}
	for(i=2;i<n;++i){
		for(j=1;j<=sum[i];++j){
			add(num[i]*2-m-sum[i]+1+j,num[i]*2-m+1+j,1,map[i][j]);
			add(num[i]*2-m-sum[i]+1+j,num[i]*2-m+2+j,1,map[i][j]);
		}
	}
	for(i=1;i<=sum[n];++i) add(num[n]*2-m-sum[n]+1+i,T,1,map[n][i]);
	for(i=2;i<=n;++i){
		for(j=1;j<=sum[i];++j){
			add(num[i-1]*2-m+1+j,num[i-1]*2-m+1+j+sum[i],1,0);
		}
	}
	minn=1;ans=0;
	while(minn){
		minn=SPFA(1,T);
		if(minn) ans+=minn*ISAP(1,T);
	}
	printf("%d\n",ans);
	/*-----------work2-----------*/
	memset(point,0,sizeof(point));
	memset(next,0,sizeof(next));
	tot=1;T=N+2;	
	for(i=1;i<=m;++i) add(1,i+1,1,0);
	for(i=1;i<n;++i){
		for(j=1;j<=sum[i];++j){
			add(1+num[i-1]+j,1+num[i-1]+j+sum[i],1,map[i][j]);
			add(1+num[i-1]+j,2+num[i-1]+j+sum[i],1,map[i][j]);
		}
	}
	for(i=1;i<=sum[n];++i) add(1+num[n-1]+i,T,m,map[n][i]);
	minn=1;ans=0;
	while(minn){
		minn=SPFA(1,T);
		if(minn) ans+=minn*ISAP(1,T);
	}
	printf("%d\n",ans);
	/*-----------work3-----------*/
	memset(point,0,sizeof(point));
	memset(next,0,sizeof(next));
	tot=1;T=N+2;	
	for(i=1;i<=m;++i) add(1,i+1,1,0);
	for(i=1;i<n;++i){
		for(j=1;j<=sum[i];++j){
			add(1+num[i-1]+j,1+num[i-1]+j+sum[i],m,map[i][j]);
			add(1+num[i-1]+j,2+num[i-1]+j+sum[i],m,map[i][j]);
		}
	}
	for(i=1;i<=sum[n];++i) add(1+num[n-1]+i,T,m,map[n][i]);
	minn=1;ans=0;
	while(minn){
		minn=SPFA(1,T);
		if(minn) ans+=minn*ISAP(1,T);
	}
	printf("%d\n",ans);
}