给你一个数字梯形， 最上面一层m个数字， 然后m+1,......m+n-1个。 n是层数。 在每个位置， 可以向左下或右下走。然后让你从最顶端的m个数字开始， 走出m条路径， 使得路过的数字总和最大。
给你三种规则， 第一种是，m条路径完全不能相交。 第二种是可以在数字处相交。 第三种是可以在数字或边的地方相交， 相当于没有限制。让你输出在这三种情况下的最大值分别是多少。
第一种， 因为完全不能相交， 所以我们将每个点拆成两个点x, x'， x向x'连一条权值为1， 费用为-a[i][j]的边。 x'向可以到达的y连一条权值1， 费用0的边。 这样保证只走一次。
第二种， 可以在点的地方相交， 那x向x'连的那条边权值就可以放松为m。 其他不变。
第三种， 不光x向x'连的边权值可以放松， x'向y连得边权值也可以放松为m。
然后就可以得出答案了。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <complex>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef complex <double> cmx;
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 2e5+;
int num, head[maxn*], s, t, n, nn, dis[maxn], flow, cost, cnt, cap[maxn], q[maxn], cur[maxn], vis[maxn], m, a[][];
struct node
{
int to, nextt, c, w;
node(){}
node(int to, int nextt, int c, int w):to(to), nextt(nextt), c(c), w(w) {}
}e[maxn*];
int spfa() {
int st, ed;
st = ed = ;
mem2(dis);
++cnt;
dis[s] = ;
cap[s] = inf;
cur[s] = -;
q[ed++] = s;
while(st<ed) {
int u = q[st++];
vis[u] = cnt-;
for(int i = head[u]; ~i; i = e[i].nextt) {
int v = e[i].to, c = e[i].c, w = e[i].w;
if(c && dis[v]>dis[u]+w) {
dis[v] = dis[u]+w;
cap[v] = min(c, cap[u]);
cur[v] = i;
if(vis[v] != cnt) {
vis[v] = cnt;
q[ed++] = v;
}
}
}
}
if(dis[t] == inf)
return ;
cost += dis[t]*cap[t];
flow += cap[t];
for(int i = cur[t]; ~i; i = cur[e[i^].to]) {
e[i].c -= cap[t];
e[i^].c += cap[t];
}
return ;
}
int mcmf() {
flow = cost = ;
while(spfa())
;
return cost;
}
void add(int u, int v, int c, int val) {
e[num] = node(v, head[u], c, val); head[u] = num++;
e[num] = node(u, head[v], , -val); head[v] = num++;
}
void init() {
mem1(head);
num = cnt = ;
mem(vis);
}
int getnum(int x, int y)
{
return (m+(x-)+m)*(x)/+y+;
}
void solve()
{
init();
t = +(*m+n-)*n;
s = ;
int sum = (*m+n-)*n/;
for(int i = ; i < n; i++) {
for(int j = ; j < m+i; j++) {
if(!i) {
add(s, j+, , );
}
int x = getnum(i, j);
add(x, x+sum, , -a[i][j]);
if(i != n-) {
int nxt = getnum(i+, j);
add(x+sum, nxt, , );
add(x+sum, nxt+, , );
}
if(i == n-) {
add(x+sum, t, , );
}
}
}
cout<<-mcmf()<<endl;
init();
for(int i = ; i < n; i++) {
for(int j = ; j < m+i; j++) {
if(!i) {
add(s, j+, , );
}
int x = getnum(i, j);
add(x, x+sum, m, -a[i][j]);
if(i != n-) {
int nxt = getnum(i+, j);
add(x+sum, nxt, , );
add(x+sum, nxt+, , );
}
if(i == n-) {
add(x+sum, t, m, );
}
}
}
cout<<-mcmf()<<endl;
init();
for(int i = ; i < n; i++) {
for(int j = ; j < m+i; j++) {
if(!i) {
add(s, j+, , );
}
int x = getnum(i, j);
add(x, x+sum, m, -a[i][j]);
if(i < n-) {
int nxt = getnum(i+, j);
add(x+sum, nxt, m, );
add(x+sum, nxt+, m, );
} else {
add(x+sum, t, m, );
}
}
}
cout<<-mcmf()<<endl;
}
int main()
{
cin>>m>>n;
for(int i = ; i < n; i++) {
for(int j = ; j < m+i; j++) {
scanf("%d", &a[i][j]);
}
}
solve();
return ;
}