题目描述

给定一个由 nn 行数字组成的数字梯形如下图所示。
数字梯形问题.png
梯形的第一行有 mm 个数字。从梯形的顶部的 mm 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。
分别遵守以下规则：
从梯形的顶至底的 mm 条路径互不相交；
从梯形的顶至底的 mm 条路径仅在数字结点处相交；
从梯形的顶至底的 mm 条路径允许在数字结点相交或边相交。

输入格式

第 11 行中有 22 个正整数 mm 和 nn，分别表示数字梯形的第一行有 mm 个数字，共有 nn 行。接下来的 nn 行是数字梯形中各行的数字。
第 11 行有 mm 个数字，第 22 行有 m+1m+1 个数字，以此类推。

输出格式

将按照规则 11，规则 22，和规则 33 计算出的最大数字总和并输出，每行一个最大总和。

输入输出样例

输入 #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⩽201\leqslant m,n \leqslant 20。

分析

1∼n1\sim n 行的数字个数呈等差数列，共有 num=n(2m+n−1)2num=\frac{n(2m+n-1)}{2} 个数字。不妨将数字看作一个点，第 ii 行 jj 列的点的编号为 (i−1)(2m+i−2)2+j\frac{(i-1)(2m+i-2)}{2}+j，记作 ID(i,j)ID(i,j)。其值作为点权，一条路径自上而下覆盖 mm 个点，费用为点权和。可以考虑使用费用流解决问题。
费用流的费用是边的单位费用，要将点权体现在边上，可进行拆点操作。对于编号为 ID(i,j)ID(i,j) 的点，将其拆成两个点 XID(i,j),YID(i,j)X_{ID(i,j)},Y_{ID(i,j)}，XID(i,j)X_{ID(i,j)} 编号为 ID(i,j)ID(i,j)，YID(i,j)Y_{ID(i,j)} 编号为 ID(i,j)+numID(i,j)+num，边上的费用为其点权值。 设置源点 ss，连接点 ID(1,1)∼ID(1,m)ID(1,1)\sim ID(1,m)，费用为 00；设置汇点 tt，ID(n,1)∼ID(n,m+n−1)ID(n,1)\sim ID(n,m+n-1) 向 tt 连边，费用为 00；对于 i<ni<n 的点，YID(i,j)Y_{ID(i,j)} 向 XID(i+1,j)X_{ID(i+1,j)} 和 XID(i+1,j+1)X_{ID(i+1,j+1)} 连边，容量为 00。对于三种不同的限制条件，要通过设置每条边的容量，使得利用 MCMF\text{MCMF} 算法求出的最大费用最大流即为答案。
首先看 ss 的出边和 tt 的入边。mm 条路径要从顶层 mm 个点出发，ss 的出边的容量应设为 11。由于最后要确定 mm 条路径，流入 tt 的流量必须为 mm；ss 出边容量设置好后，网络最大流必然不超过 mm，因此直接设 tt 的入边流量都为 +∞+\infty 即可。
第一种限制条件，从梯形的顶至底的 mm 条路径互不相交。可以将 XID(i,j)X_{ID(i,j)} 和 YID(i,j)Y_{ID(i,j)} 之间边的容量设为 11，表示每个数字只能使用一次，路径不能有相交的点；再将 YID(i,j)Y_{ID(i,j)} 向 XID(i+1,j)X_{ID(i+1,j)} 和 XID(i+1,j+1)X_{ID(i+1,j+1)} 连边的容量设为 11，表示路径不能有相交的边。实际上，“路径没有相交的点”是一个比“路径没有相交的边”更强的条件，将 XID(i,j)X_{ID(i,j)} 和 YID(i,j)Y_{ID(i,j)} 之间边的容量设为 11 即可。
第二种限制条件，从梯形的顶至底的 mm 条路径仅在数字结点处相交。可以将 XID(i,j)X_{ID(i,j)} 和 YID(i,j)Y_{ID(i,j)} 之间边的容量设为 +∞+\infty，路径可以能有相交的点；再将 YID(i,j)Y_{ID(i,j)} 向 XID(i+1,j)X_{ID(i+1,j)} 和 XID(i+1,j+1)X_{ID(i+1,j+1)} 连边的容量设为 11，表示路径不能有相交的边。
第三种限制条件，从梯形的顶至底的 mm 条路径允许在数字结点相交或边相交。可以将 XID(i,j)X_{ID(i,j)} 和 YID(i,j)Y_{ID(i,j)} 之间边的容量设为 +∞+\infty，路径可以能有相交的点；再将 YID(i,j)Y_{ID(i,j)} 向 XID(i+1,j)X_{ID(i+1,j)} 和 XID(i+1,j+1)X_{ID(i+1,j+1)} 连边的容量设为 +∞+\infty，表示路径能有相交的边。
对三种条件各建一张图，求最大费用最大流即可。

代码

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
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P4013
Date: 8/5/2020
Description: Maximum-cost Flow
*******************************************************************/
#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;//剩余容量为0，不在残量网络中。
			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\text{TLE} 了。