【网络流24题-16】数字梯形问题费用流

2019-11-06 07:05:27

字体：大中小

来源：转载

供稿：网友

题目描述

　　给定一个由 n 行数字组成的数字梯形如下图所示。梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。　　规则1：从梯形的顶至底的m条路径互不相交。　　规则2：从梯形的顶至底的m条路径仅在数字结点处相交。　　规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。　　对于给定的数字梯形，分别按照规则1，规则2，和规则 3 计算出从梯形的顶至底的 m条路径，使这 m条路径经过的数字总和最大。 233

数据范围

（m,n<=20）

样例输入

2 5 2 3 3 4 5 9 10 9 1 1 1 10 1 1 1 1 10 12 1 1

样例输出

66 75 77

解题思路

这道题强行将三道题揉成了一道题，但这也有助于对边的限制于点的限制的理解。首先，将点p拆成p1,p2,p1于p2之间的容量就是点的限制 ①：m条路径不相交　　只要点不相交，边就不会相交，路径就不会相交。　　所以S向顶层的p1连一条容量1，费用0的有向边　　每一层的p2向下一层相邻的两个点的p1连一条容量1，费用0的有向边　　对于每个点p1向p2连一条容量为1，费用为权值的有向边　　然后最大费用最大流 ②：边不相交　　将p1向p2连的边的容量改为inf 　　然后最大费用最大流 ③：没有限制　　可以用dp，也可以将两层之间连的边容量改为inf，然后最大费用最大流关于最大费用最大流的求法，可以将边的费用取相反数，最后的答案也取相反数

代码

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <ctime>#include <queue>#define Maxn 233333#define Maxe 233333using namespace std;inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int cnt=0,h[Maxn],dis[Maxn],PRe[Maxn],preto[Maxn],vis[Maxn],S=0,T;struct node{int to,next,v,k,pair;}e[Maxe],e2[Maxe];void AddEdge(int x,int y,int v,int kk,int pair){e[cnt]=(node){y,h[x],v,kk,pair};h[x]=cnt;}void AddEdge(int x,int y,int v,int kk){AddEdge(x,y,v,kk,++cnt+1);AddEdge(y,x,0,-kk,++cnt-1);}bool SPFA(){ queue<int>Q; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(pre,0,sizeof(pre)); memset(preto,0,sizeof(preto)); dis[S]=0; vis[S]=1; Q.push(S); while(Q.size()){ int x=Q.front(); Q.pop(); vis[x]=false; for(int p=h[x];p;p=e[p].next){ int y=e[p].to; if(e[p].v&&dis[y]>dis[x]+e[p].k){ pre[y]=p; preto[y]=x; dis[y]=dis[x]+e[p].k; if(!vis[y])Q.push(y); } } } return dis[T]<=(1<<29);}int Adjust(){ int flow=1<<30; for(int p=T;p!=S;p=preto[p]) flow=min(flow,e[pre[p]].v); for(int p=T;p!=S;p=preto[p]){ e[pre[p]].v-=flow; e[e[pre[p]].pair].v+=flow; } return dis[T]*flow;}int Solve(){ memcpy(e2,e,sizeof(e)); int Ans=0; while(SPFA())Ans+=Adjust(); memcpy(e,e2,sizeof(e2)); return Ans;}int m,n,Map[25][45],ha[25][45],tot=0;void Init(){ m=Getint(),n=Getint(); for(int i=1;i<=n;i++) for(int j=1;j<=m+i-1;j++) Map[i][j]=Getint(),ha[i][j]=++tot;}void Build(){ S=0,T=tot*2+1; for(int i=1;i<=m;i++)AddEdge(S,i,1,0); for(int i=1;i<=n;i++) for(int j=1;j<=m+i-1;j++) AddEdge(ha[i][j],ha[i][j]+tot,1,-Map[i][j]); for(int i=1;i<n;i++) for(int j=1;j<=m+i-1;j++) AddEdge(ha[i][j]+tot,ha[i+1][j],1,0),AddEdge(ha[i][j]+tot,ha[i+1][j+1],1,0); for(int j=1;j<=m+n-1;j++)AddEdge(ha[n][j]+tot,T,1,0);}void BuildAgain(){ for(int i=1;i<=n;i++) for(int j=1;j<=m+i-1;j++) AddEdge(ha[i][j],ha[i][j]+tot,1<<30,-Map[i][j]); for(int j=1;j<=m+n-1;j++)AddEdge(ha[n][j]+tot,T,1<<30,0);}void BuildAgainAndAgain(){ for(int i=1;i<n;i++) for(int j=1;j<=m+i-1;j++) AddEdge(ha[i][j]+tot,ha[i+1][j],1<<30,0),AddEdge(ha[i][j]+tot,ha[i+1][j+1],1<<30,0);}int main(){ Init(); Build(); cout<<-Solve()<<"/n"; BuildAgain(); cout<<-Solve()<<"/n"; BuildAgainAndAgain(); cout<<-Solve()<<"/n";}

上一篇：399. Evaluate Division

下一篇：412. Fizz Buzz