loj6010「网络流 24 题」数字梯形

loj6010「网络流 24 题」数字梯形

(​​ 题目描述

给定一个由 n n n 行数字组成的数字梯形如下图所示。梯形的第一行有 m m m 个数字。从梯形的顶部的 m m m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。

分别遵守以下规则：

从梯形的顶至底的 m m m 条路径互不相交；从梯形的顶至底的 m m m 条路径仅在数字结点处相交；从梯形的顶至底的 m m m 条路径允许在数字结点相交或边相交。

输入格式

第 1 1 1 行中有 2 2 2 个正整数 m m m 和 n n n，分别表示数字梯形的第一行有 m m m 个数字，共有 n n n 行。接下来的 n n n 行是数字梯形中各行的数字。 第 1 1 1 行有 m m m 个数字，第 2 2 2 行有 m+1 m + 1 m+1 个数字 …… 输出格式

将按照规则 1，规则 2，和规则 3 计算出的最大数字总和并输出，每行一个最大总和。 样例 样例输入

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

数据范围与提示

1≤m,n≤20 1 \leq m, n \leq 20 1≤m,n≤20

一个等腰梯形 每次可以走左下和右下那么意味着 我可以走i+1,j或者i+1,j+1

那我就把每个点 拆成两个点 中间 限制流量为1 然后费用为那个点的权值 然后我从源点向汇点跑最大流即可，最大费用最大流；

第一问 路径不可以相交 也就是每个点都只可以经过一次 然后每个上面的点都和源点连接 下面的点都和汇点连接

第二问 只需要把拆开的点之间的容量改成无限即可 然后还有最后一行到汇点的容量改成无限

第三问 第三问 边也可以相交 那么直接把原来所有的边的容量都改成无限即可

#include#include#include#include#define inf 0x3f3f3f3f#define N 2200using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int x,y,z,c,next;}data[N<<1];int f[N],m,n,pre[N],path[N],num,h[N],T,mp[50][50],nm[50][50];bool flag[N];inline void insert1(int x,int y,int z,int c){ data[++num].y=y;data[num].z=z;data[num].c=c;data[num].next=h[x];h[x]=num;data[num].x=x; data[++num].y=x;data[num].z=0;data[num].c=-c;data[num].next=h[y];h[y]=num;data[num].x=y;}inline int calc(int i,int j){return (m+m+(i-2))*(i-1)/2+j;}inline bool spfa(){ queueq;memset(flag,0,sizeof(flag));memset(f,128,sizeof(f));f[0]=0;flag[0]=1;q.push(0);memset(pre,-1,sizeof(pre)); while(!q.empty()){ int x=q.front();q.pop();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z,c=data[i].c; if (f[x]+c>f[y]&&z){ f[y]=f[x]+c;pre[y]=x;path[y]=i; if(!flag[y]) flag[y]=1,q.push(y); } } }if (pre[T]==-1) return 0;else return 1;}int main(){ freopen("loj.in","r",stdin); m=read();n=read();int len=m,top=m,down=m+n-1,nn=(top+down)*n/2;T=nn*2+1; for (int i=1;i<=n;++i){ for (int j=1;j<=len;++j) mp[i][j]=read(),nm[i][j]=calc(i,j);len++; }len=m;num=1;T=nn*2+1; for (int i=1;i<=n;++i){ for (int j=1;j<=len;++j) { if (i==1)insert1(0,nm[i][j],1,0);insert1(nm[i][j],nm[i][j]+nn,1,mp[i][j]); if (i!=n){ insert1(nm[i][j]+nn,nm[i+1][j],1,0);insert1(nm[i][j]+nn,nm[i+1][j+1],1,0); }else{ insert1(nm[i][j]+nn,T,1,0); } }len++; }int ans=0; //for (int i=2;i<=num;++i) if (data[i].c>0)printf("%d %d %d %d\n",data[i].x,data[i].y,data[i].z,data[i].c); while(spfa()){ int now=T,minn=inf; while(now) {minn=min(minn,data[path[now]].z);now=pre[now];}now=T; while(now){ans+=minn*data[path[now]].c;data[path[now]].z-=minn;data[path[now]^1].z+=minn;now=pre[now];} }printf("%d\n",ans);ans=0;memset(h,0,sizeof(h));len=m;num=1; for (int i=1;i<=n;++i){ for (int j=1;j<=len;++j) { if (i==1)insert1(0,nm[i][j],1,0);insert1(nm[i][j],nm[i][j]+nn,inf,mp[i][j]); if (i!=n){ insert1(nm[i][j]+nn,nm[i+1][j],1,0);insert1(nm[i][j]+nn,nm[i+1][j+1],1,0); }else{ insert1(nm[i][j]+nn,T,inf,0); } }len++; } while(spfa()){ int now=T,minn=inf; while(now) {minn=min(minn,data[path[now]].z);now=pre[now];}now=T; while(now){ans+=minn*data[path[now]].c;data[path[now]].z-=minn;data[path[now]^1].z+=minn;now=pre[now];} }printf("%d\n",ans);ans=0;memset(h,0,sizeof(h));len=m;num=1; for (int i=1;i<=n;++i){ for (int j=1;j<=len;++j) { if (i==1)insert1(0,nm[i][j],1,0);insert1(nm[i][j],nm[i][j]+nn,inf,mp[i][j]); if (i!=n){ insert1(nm[i][j]+nn,nm[i+1][j],inf,0);insert1(nm[i][j]+nn,nm[i+1][j+1],inf,0); }else{ insert1(nm[i][j]+nn,T,inf,0); } }len++; } while(spfa()){ int now=T,minn=inf; while(now) {minn=min(minn,data[path[now]].z);now=pre[now];}now=T; while(now){ans+=minn*data[path[now]].c;data[path[now]].z-=minn;data[path[now]^1].z+=minn;now=pre[now];} }printf("%d",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。