数字梯形问题

题目描述
给定一个由 nn 行数字组成的数字梯形如下图所示。

梯形的第一行有 mm 个数字。从梯形的顶部的 mm 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。

分别遵守以下规则：

从梯形的顶至底的 mm 条路径互不相交；

从梯形的顶至底的 mm 条路径仅在数字结点处相交；

从梯形的顶至底的 mm 条路径允许在数字结点相交或边相交。

输入格式
第 11 行中有 22 个正整数 mm 和 nn，分别表示数字梯形的第一行有 mm 个数字，共有 nn 行。接下来的 nn 行是数字梯形中各行的数字。

第 11 行有 mm 个数字，第 22 行有 m+1m+1 个数字，以此类推。

输出格式
将按照规则 11，规则 22，和规则 33 计算出的最大数字总和并输出，每行一个最大总和。

输入输出样例
输入 #1 复制
2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1
输出 #1 复制
66
75
77
说明/提示
1\leq m,n \leq 201≤m,n≤20

第一问，直接拆点限流。

第二问，直接不同点之间限流。

第三问，直接不用限制，只限制S出来的流。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
#define num(i,j) ((n+m)*(i-1)+j)
using namespace std;
const int inf=0x3f3f3f3f;
const int N=10010,M=2000010;
int m,n,s,t,g[55][55],d[N],v[N],e[N];
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	w[++tot]=d; flow[tot]=c; to[tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(){
	memset(d,0xcf,sizeof d);	d[s]=0;	queue<int> q;	q.push(s);
	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=0xcfcfcfcf;
}
int EK(){
	int res=0;
	while(spfa()){
		int mi=0x3f3f3f3f;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=d[t]*mi;
	}
	return res;
}
signed main(){
	cin>>m>>n;	s=0;	t=(n+m)*(n+m)*4+1000;	int base=(n+m)*(n+m)*2;
	for(int i=1;i<=n;i++)	for(int j=1;j<i+m;j++)	cin>>g[i][j];
	for(int i=1;i<=m;i++)	add(s,num(1,i),1,0);
	for(int i=1;i<n;i++){
		for(int j=1;j<i+m;j++){
			add(num(i,j)+base,num(i+1,j),1,0);
			add(num(i,j)+base,num(i+1,j+1),1,0);
		}
	}
	for(int i=1;i<n+m;i++)	add(num(n,i)+base,t,1,0);
	for(int i=1;i<=n;i++)	
		for(int j=1;j<i+m;j++)
			add(num(i,j),num(i,j)+base,1,g[i][j]);
	cout<<EK()<<endl;
	tot=1;	memset(head,0,sizeof head);
	for(int i=1;i<=m;i++)	add(s,num(1,i),1,0);
	for(int i=1;i<n;i++){
		for(int j=1;j<i+m;j++){
			add(num(i,j),num(i+1,j),1,g[i][j]);
			add(num(i,j),num(i+1,j+1),1,g[i][j]);
		}
	}
	for(int i=1;i<m+n;i++)	add(num(n,i),t,inf,g[n][i]);
	cout<<EK()<<endl;
	tot=1;	memset(head,0,sizeof head);
	for(int i=1;i<=m;i++)	add(s,num(1,i),1,0);
	for(int i=1;i<n;i++){
		for(int j=1;j<i+m;j++){
			add(num(i,j),num(i+1,j),inf,g[i][j]);
			add(num(i,j),num(i+1,j+1),inf,g[i][j]);
		}
	}
	for(int i=1;i<m+n;i++)	add(num(n,i),t,inf,g[n][i]);
	cout<<EK()<<endl;
	return 0;
}