738. [网络流24题] 数字梯形
问题描述：给定一个由n 行数字组成的数字梯形如下图所示。梯形的第一行有m 个数字。从梯形的顶部的m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。规则1：从梯形的顶至底的m条路径互不相交。规则2：从梯形的顶至底的m条路径仅在数字结点处相交。规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。
编程任务：对于给定的数字梯形，分别按照规则1，规则2，和规则3 计算出从梯形的顶至底的m条路径，使这m条路径经过的数字总和最大。数据输入：由文件digit.in提供输入数据。文件的第1 行中有2个正整数m和n（m,n<=20），分别表示数字梯形的第一行有m个数字，共有n 行。接下来的n 行是数字梯形中各行的数字。第1 行有m个数字，第2 行有m+1 个数字，…。结果输出:程序运行结束时，将按照规则1，规则2，和规则3 计算出的最大数字总和输出到文件digit.out中。每行一个最大总和。输入文件示例 输出文件示例digit.in2 52 33 4 59 10 9 11 1 10 1 1
1 1 10 12 1 1
digit.out
667577
这道题算是三个网络流合成一体。。难度却是递减的。。
<1>对于第一个规则，因为需要不相交，所以要拆点。将i拆成ia和ib，然后ia和ib之间连一条流量为1，费用为i的值的边。接下来在符合从上到下的移动规矩的ib,ja之间连一条流量为1，费用为0的边。然后再从虚拟源点向第一排的每个点，最后一排的每个点向虚拟汇点，分别连一条流量为1，费用为0的点。
<2>对于第二个规则，因为可以顶点相交，所以不需要拆点。直接在符合从上到下的移动规矩的i,j之间连一条流量为1，费用为j的值。然后再从虚拟源点向第一排的每一个点连一条流量为1，费用为i的值。最后从最后一排的每个点向虚拟汇点，连一条流量为无穷，费用为0的点。
<3>对于第三个规则，因为没有限制，所以直接可以在<2>的基础上改动一个地方，即在符合从上到下的移动规矩的i,j之间连的是一条流量为无穷，，费用为j的值。其余和<2>一样。
Code：
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#define N 100010#define inf 0x7fffffffusing namespace std;struct Edge{int v,next,res,cost;inline void newEdge(){v=next=res=cost=0;}}edge[N];int n,m,num=1,ans,tot,sum,S,T,map[51][51];int flow[N],prep[N],prev[N],dis[N],g[N],que[10*N];bool vis[N];inline int in(){int x=0; char ch=getchar();while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x;}inline void add(int u,int v,int cap,int cost){edge[++num].v=v; edge[num].next=g[u]; g[u]=num;edge[num].res=cap; edge[num].cost=cost;}inline void clean(){for (int i=1; i<=num; i++) edge[i].newEdge();memset(g,0,sizeof(g)); num=1;}inline bool spfa(){int h=0,t=1;memset(dis,0x7f,sizeof(dis));memset(vis,false,sizeof(vis));dis[S]=0; vis[S]=true; prep[S]=-1;flow[S]=inf; que[0]=S;while (h<t){int u=que[h++]; vis[u]=false;for (int i=g[u]; i; i=edge[i].next){int v=edge[i].v;if (edge[i].res>0 && dis[v]>dis[u]+edge[i].cost){dis[v]=dis[u]+edge[i].cost;prep[v]=u; prev[v]=i;flow[v]=min(flow[u],edge[i].res);if (!vis[v]) vis[v]=true,que[t++]=v;}}}if (dis[T]>0x7ffffff) return false;for (int i=T; i!=S; i=prep[i]){edge[prev[i]].res-=flow[T];edge[prev[i]^1].res+=flow[T];}ans+=flow[T]*dis[T];return true;}inline void work1(){ans=tot=0;for (int i=1; i<=n; i++)for (int j=1; j<=m+i-1; j++){tot++;add(tot,tot+sum,1,-map[i][j]),add(tot+sum,tot,0,map[i][j]);}tot=0;for (int i=1; i<n; i++)for (int j=1; j<=m+i-1; j++){tot++; int k=(2*m+i-1)*(i/2)+(i%2==0 ? 0 : m+(i/2));add(tot+sum,k+j,1,0),add(k+j,tot+sum,0,0);add(tot+sum,k+j+1,1,0),add(k+j+1,tot+sum,0,0);}for (int i=1; i<=m; i++)add(S,i,1,0),add(i,S,0,0);for (int i=1; i<=m+n-1; i++)add(2*sum-m-n+i+1,T,1,0),add(T,2*sum-m-n+i+1,0,0);while (spfa());printf("%d\n",-ans);}inline void work2(){ans=tot=0; S=0; T=sum+1; clean();for (int i=1; i<n; i++)for (int j=1; j<=m+i-1; j++){tot++; int k=(2*m+i-1)*(i/2)+(i%2==0 ? 0 : m+(i/2));add(tot,k+j,1,-map[i+1][j]),add(k+j,tot,0,map[i+1][j]);add(tot,k+j+1,1,-map[i+1][j+1]),add(k+j+1,tot,0,map[i+1][j+1]);}for (int i=1; i<=m; i++)add(S,i,1,-map[1][i]),add(i,S,0,map[1][i]);for (int i=1; i<=m+n-1; i++)add(sum-m-n+i+1,T,inf,0),add(T,sum-m-n+i+1,0,0);while (spfa());printf("%d\n",-ans);}inline void work3(){ans=tot=0; S=0; T=sum+1; clean();for (int i=1; i<n; i++)for (int j=1; j<=m+i-1; j++){tot++; int k=(2*m+i-1)*(i/2)+(i%2==0 ? 0 : m+(i/2));add(tot,k+j,inf,-map[i+1][j]),add(k+j,tot,0,map[i+1][j]);add(tot,k+j+1,inf,-map[i+1][j+1]),add(k+j+1,tot,0,map[i+1][j+1]);}for (int i=1; i<=m; i++)add(S,i,1,-map[1][i]),add(i,S,0,map[1][i]);for (int i=1; i<=m+n-1; i++)add(sum-m-n+i+1,T,inf,0),add(T,sum-m-n+i+1,0,0);while (spfa());printf("%d\n",-ans);}int main(){freopen("digit.in","r",stdin);freopen("digit.out","w",stdout);m=in(),n=in();for (int i=1; i<=n; i++)for (int j=1; j<=m+i-1; j++)map[i][j]=in();sum=(2*m+n-1)*(n/2)+(n%2==0 ? 0 : (m+(n/2)));S=0; T=(sum<<1)+1;work1();//规则一 work2();//规则二 work3();//规则三 return 0;}
没有什么可凭仗，只有他的好身体，没有地方可去，只想到处流浪。
