题目描述
给定一个由 n 行数字组成的数字梯形如下图所示。
梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。
分别遵守以下规则:
从梯形的顶至底的 m 条路径互不相交;
从梯形的顶至底的 m 条路径仅在数字结点处相交;
从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。
输入格式
第 1 行中有 2 个正整数 m 和 n,分别表示数字梯形的第一行有 m 个数字,共有 n 行。接下来的 n 行是数字梯形中各行的数字。
第 1 行有 m 个数字,第 2 行有 m+1 个数字,以此类推。
输出格式
将按照规则 1,规则 2,和规则 3 计算出的最大数字总和并输出,每行一个最大总和。
输入输出样例
输入 #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⩽m,n⩽20。
分析
1∼n 行的数字个数呈等差数列,共有 num=2n(2m+n−1) 个数字。不妨将数字看作一个点,第 i 行 j 列的点的编号为 2(i−1)(2m+i−2)+j,记作 ID(i,j)。其值作为点权,一条路径自上而下覆盖 m 个点,费用为点权和。可以考虑使用费用流解决问题。
费用流的费用是边的单位费用,要将点权体现在边上,可进行拆点操作。对于编号为 ID(i,j) 的点,将其拆成两个点 XID(i,j),YID(i,j),XID(i,j) 编号为 ID(i,j),YID(i,j) 编号为 ID(i,j)+num,边上的费用为其点权值。 设置源点 s,连接点 ID(1,1)∼ID(1,m),费用为 0;设置汇点 t,ID(n,1)∼ID(n,m+n−1) 向 t 连边,费用为 0;对于 i<n 的点,YID(i,j) 向 XID(i+1,j) 和 XID(i+1,j+1) 连边,容量为 0。对于三种不同的限制条件,要通过设置每条边的容量,使得利用 MCMF 算法求出的最大费用最大流即为答案。
首先看 s 的出边和 t 的入边。m 条路径要从顶层 m 个点出发,s 的出边的容量应设为 1。由于最后要确定 m 条路径,流入 t 的流量必须为 m;s 出边容量设置好后,网络最大流必然不超过 m,因此直接设 t 的入边流量都为 +∞ 即可。
第一种限制条件,从梯形的顶至底的 m 条路径互不相交。可以将 XID(i,j) 和 YID(i,j) 之间边的容量设为 1,表示每个数字只能使用一次,路径不能有相交的点;再将 YID(i,j) 向 XID(i+1,j) 和 XID(i+1,j+1) 连边的容量设为 1,表示路径不能有相交的边。实际上,“路径没有相交的点”是一个比“路径没有相交的边”更强的条件,将 XID(i,j) 和 YID(i,j) 之间边的容量设为 1 即可。
第二种限制条件,从梯形的顶至底的 m 条路径仅在数字结点处相交。可以将 XID(i,j) 和 YID(i,j) 之间边的容量设为 +∞,路径可以能有相交的点;再将 YID(i,j) 向 XID(i+1,j) 和 XID(i+1,j+1) 连边的容量设为 1,表示路径不能有相交的边。
第三种限制条件,从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。可以将 XID(i,j) 和 YID(i,j) 之间边的容量设为 +∞,路径可以能有相交的点;再将 YID(i,j) 向 XID(i+1,j) 和 XID(i+1,j+1) 连边的容量设为 +∞,表示路径能有相交的边。
对三种条件各建一张图,求最大费用最大流即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
|
#include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int inf=0x3f3f3f3f; const int N=2003; struct E { int to; int cap; int cost; int Next; }; E edge[N<<6]; int head[N],tot; int incf[N],pre[N]; int dis[N]; bool inqueue[N]; int m,n,num; int s,t; int a[N][N]; void init(); int ID(int,int); inline void add_edge(int,int,int,int); bool SPFA(); int MCMF(); int main() { cin>>m>>n; int i,j; for(i=1;i<=n;i++) { for(j=1;j<=m+i-1;j++) { scanf("%d",&a[i][j]); } } init(); for(i=1;i<=n;i++) { for(j=1;j<=m+i-1;j++) { if(i==1) add_edge(s,ID(i,j),1,0); if(i==n) add_edge(ID(i,j)+num,t,inf,0); if(i<n) { add_edge(ID(i,j)+num,ID(i+1,j),1,0); add_edge(ID(i,j)+num,ID(i+1,j+1),1,0); } add_edge(ID(i,j),ID(i,j)+num,1,-a[i][j]); } } cout<<-MCMF()<<endl; init(); for(i=1;i<=n;i++) { for(j=1;j<=m+i-1;j++) { if(i==1) add_edge(s,ID(i,j),1,0); if(i==n) add_edge(ID(i,j)+num,t,inf,0); if(i<n) { add_edge(ID(i,j)+num,ID(i+1,j),1,0); add_edge(ID(i,j)+num,ID(i+1,j+1),1,0); } add_edge(ID(i,j),ID(i,j)+num,inf,-a[i][j]); } } cout<<-MCMF()<<endl; init(); for(i=1;i<=n;i++) { for(j=1;j<=m+i-1;j++) { if(i==1) add_edge(s,ID(i,j),1,0); if(i==n) add_edge(ID(i,j)+num,t,inf,0); if(i<n) { add_edge(ID(i,j)+num,ID(i+1,j),inf,0); add_edge(ID(i,j)+num,ID(i+1,j+1),inf,0); } add_edge(ID(i,j),ID(i,j)+num,inf,-a[i][j]); } } cout<<-MCMF()<<endl; return 0; } void init() { tot=1; num=(2*m+n-1)*n/2; memset(head,-1,sizeof(head)); s=0; t=num*2+1; } inline void add_edge(int u,int v,int cap,int cost) { tot++; edge[tot].to=v; edge[tot].cap=cap; edge[tot].cost=cost; edge[tot].Next=head[u]; head[u]=tot; tot++; edge[tot].to=u; edge[tot].cap=0; edge[tot].cost=-cost; edge[tot].Next=head[v]; head[v]=tot; } bool SPFA() { queue<int>q; memset(dis,inf,sizeof(dis)); memset(inqueue,0,sizeof(inqueue)); q.push(s); dis[s]=0; inqueue[s]=1; incf[s]=inf; while(!q.empty()) { int x=q.front(); q.pop(); inqueue[x]=0; for(register int i=head[x];~i;i=edge[i].Next) { if(!edge[i].cap) continue; int y=edge[i].to; if(dis[y]>dis[x]+edge[i].cost) { dis[y]=dis[x]+edge[i].cost; incf[y]=min(incf[x],edge[i].cap); pre[y]=i; if(!inqueue[y]) { inqueue[y]=1; q.push(y); } } } } if(dis[t]==inf) return 0; else return 1; } int MCMF() { int maxflow,mincost; maxflow=mincost=0; while(SPFA()) { int x=t; while(x!=s) { int y=pre[x]; edge[y].cap-=incf[t]; edge[y^1].cap+=incf[t]; x=edge[y^1].to; } maxflow+=incf[t]; mincost+=dis[t]*incf[t]; } return mincost; } int ID(int x,int y) {return (2*m+x-2)*(x-1)/2+y;}
|
后记
数组要开大些,若越界后动了其他地方的内存,就 TLE 了。