#include<bits/stdc++.h>
using namespace std;
const int N=420,M=1e5+100;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],incf[N],q[N],pre[N];
bool st[N];
int n,m,S,T;
int a[50][50];
int id[50][50];
void add(int a,int b,int c,int d){
e[idx]=b; f[idx]=c; w[idx]=d; ne[idx]=h[a]; h[a]=idx++;
e[idx]=a; f[idx]=0,w[idx]=-d; ne[idx]=h[b]; h[b]=idx++;
}
bool spfa(){
int hh=0,tt=1;
memset(d,-0x3f,sizeof d);
memset(incf,0,sizeof incf);
memset(st,0,sizeof st);
q[0]=S; d[S]=0; incf[S]=1e8;
while(hh!=tt){
int t=q[hh++];
if(hh==N)hh=0;
st[t]=0;
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(f[i]&&d[j]<d[t]+w[i]){
d[j]=d[t]+w[i];
pre[j]=i;
incf[j]=min(f[i],incf[t]);
if(!st[j]){
st[j]=1;
q[tt++]=j;
if(tt==N)tt=0;
}
}
}
}
return incf[T]>0;
}
int EK(int &flow,int &cost){
flow=0; cost=0;
while(spfa()){
int t=incf[T];
flow+=t; cost+=d[T]*t;
for(int i=T;i!=S;i=e[pre[i]^1]){
f[pre[i]]-=t; f[pre[i]^1]+=t;
}
}
}
int main(){
scanf("%d%d",&m,&n);
int cnt=0;
S=++cnt;
T=++cnt;
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
scanf("%d",&a[i][j]);
id[i][j]=++cnt;
}
}
memset(h,-1,sizeof h);
add(S,S+cnt,m,0);
add(T,T+cnt,m,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
int ww=a[i][j];
add(id[i][j],id[i][j]+cnt,1,ww);
if(i==1){
add(S+cnt,id[i][j],1,0);
}
else if(i==n){
add(id[i][j]+cnt,T,1,0);
}
if(i<n){
add(id[i][j]+cnt,id[i+1][j],1,0);
add(id[i][j]+cnt,id[i+1][j+1],1,0);
}
}
}
int cost,flow;
EK(flow,cost);
cout<<cost<<endl;
memset(h,-1,sizeof h);
idx=0;
add(S,S+cnt,m,0);
add(T,T+cnt,m,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
int ww=a[i][j];
add(id[i][j],id[i][j]+cnt,1e8,ww);
if(i==1){
add(S+cnt,id[i][j],1,0);
}
else if(i==n){
add(id[i][j]+cnt,T,1e8,0);
}
if(i<n){
add(id[i][j]+cnt,id[i+1][j],1,0);
add(id[i][j]+cnt,id[i+1][j+1],1,0);
}
}
}
EK(flow,cost);
cout<<cost<<endl;
memset(h,-1,sizeof h);
idx=0;
add(S,S+cnt,m,0);
add(T,T+cnt,m,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
int ww=a[i][j];
add(id[i][j],id[i][j]+cnt,1e8,ww);
if(i==1){
add(S+cnt,id[i][j],1,0);
}
else if(i==n){
add(id[i][j]+cnt,T,m,0);
}
if(i<n){
add(id[i][j]+cnt,id[i+1][j],1e8,0);
add(id[i][j]+cnt,id[i+1][j+1],1e8,0);
}
}
}
T=T+cnt;
EK(flow,cost);
cout<<cost<<endl;
}
充分考验网络流建图能力，，nb题啊，，，
首先这个题，点经过的次数也是有限制的，所以要拆点，，
y总是 给每个点一个编号 这个编号两倍 与 这个编号两倍加一 形成出点和入点
我是 这个点的编号 与 这个点的编号加原图的总点数 形成出点和入点
只要点与点的出点和入点不重复就行
第一种情况
规则 1：从梯形的顶至底的 m 条路径互不相交。
即 拆点后 点之间的边大小只能有1 然后就是 外面的边之间也只能有1
int ww=a[i][j];
add(id[i][j],id[i][j]+cnt,1,ww);
if(i==1){
add(S+cnt,id[i][j],1,0);//
}
else if(i==n){
add(id[i][j]+cnt,T,1,0);
}
if(i<n){
add(id[i][j]+cnt,id[i+1][j],1,0);
add(id[i][j]+cnt,id[i+1][j+1],1,0);
}
规则 2：从梯形的顶至底的 m 条路径仅在数字结点处相交。
那么点与点之间的边的限制就被打开了，，，给它扔一个正无穷，，
但是只把
add(id[i][j],id[i][j]+cnt,1,ww)
的1改成正无穷还是不对的，，
最后一行的连T的边的容量1也要改成正无穷，，题目说数字节点处可以相交，，那么到了最后一行的同一个数字 大家可以一起走到T
然后这种情况下 这个数字到T的这条边的容量就爆1了，， 至少要改成m次，
规则 3：从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。
那么点和边的容量，就全放开了，，高兴的我直接把所以的1变成了1e8
然后就wa了
if(i==1){
add(S+cnt,id[i][j],1,0);
}
这个1不能变成1e8
因为起点是不能相同的，，题上有说，，
然后其它的地方开心的1e8就完事了，
改变边的容量 对整个图的最大流的限制 就是经过这条边的从S到T的通路 的最小值，
二分图匹配问题 可以看成给这个物品 找几个对象
寻路问题 如果其它的边容量都是1的话，， 可以看成能经过这条边几次，（点也可以通过拆点变成边）
更一般的 边的容量不仅仅是1的话，，
可以看成每个节点都是 这个节点所有入边的流量 与 出边的流量的权衡
流量守恒这个规则
对立和统一 ？
统一的方面：大家身上都有这么多流量，，
对立的方面 ： 入边这么多流量 出边也有这么多流量 我们可以来抵消一下
