洛谷P4013 数字梯形问题(费用流)

题目描述

给定一个由 nnn 行数字组成的数字梯形如下图所示。

梯形的第一行有 mmm 个数字。从梯形的顶部的 mmm 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

  1. 从梯形的顶至底的 mmm 条路径互不相交;
  2. 从梯形的顶至底的 mmm 条路径仅在数字结点处相交;
  3. 从梯形的顶至底的 mmm 条路径允许在数字结点相交或边相交。

输入输出格式

输入格式:

第 111 行中有 222 个正整数 mmm 和 nnn ,分别表示数字梯形的第一行有 mmm 个数字,共有 nnn 行。接下来的 nnn 行是数字梯形中各行的数字。

第 111 行有 mmm 个数字,第 222 行有 m+1m+1m+1 个数字,以此类推。

输出格式:

将按照规则 111 ,规则 222 ,和规则 333 计算出的最大数字总和并输出,每行一个最大总和。

输入输出样例

输入样例#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\leq m,n \leq 201≤m,n≤20

我只会第一问qwq。。

因为有数量的限制,考虑拆点建图,把每个点拆为$a_1$和$b_1$,两点之间连流量为$1$,费用为权值的边

从$b_i$向下方和右下的$a_1$连一条流量为$1$,费用为$0$边

从$S$向第一层的$a_1$连流量为$1$,费用为$0$的边,从$b_N$到$T$连流量为$1$,费用为$0$的边

对于第二问,因为没有点的个数的限制,那么就不用拆点了,直接向能到达的点连流量为$1$,费用为点权的边

对于第三问,直接把第二问中的所有边为流量设为$INF$(除了从$S$出发的)

// luogu-judger-enable-o2
/*
因为有数量的限制,考虑拆点建图,把每个点拆为$a_1$和$b_1$,两点之间连流量为$1$,费用为权值的边

从$b_i$向下方和右下的$a_1$连一条流量为$1$,费用为$0$边

从$S$向第一层的$a_1$连流量为$1$,费用为$0$的边,从$b_N$到$T$连流量为$1$,费用为$0$的边



对于第二问,因为没有点的个数的限制,那么就不用拆点了,直接向能到达的点连流量为$1$,费用为点权的边

对于第三问,直接把第二问中的所有边为流量设为$INF$(除了从$S$出发的)
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, S = 0, T = 1e5 + 1;
int a[21][21];
struct Edge {
    int u, v, w, f, nxt;
}E[MAXN];
int head[MAXN << 1], num = 0;
inline void add_edge(int x, int y, int w, int f) {

    E[num] = (Edge){x, y, w, f, head[x]};
    head[x] = num++;    
}
inline void AddEdge(int x, int y, int w, int f) {
    add_edge(x, y, w, f);
    add_edge(y, x, -w, 0);
}
int anscost, dis[MAXN], vis[MAXN], Pre[MAXN];
bool SPFA() {
    memset(dis, -0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q; q.push(S); dis[S] = 0;
    while(!q.empty()) {
        int p = q.front(); q.pop(); vis[p] = 0;
        for(int i = head[p]; i !=- 1; i = E[i].nxt) {
            int to = E[i].v;
            if((dis[to] < dis[p] + E[i].w) && E[i].f > 0) {
                dis[to] = dis[p] + E[i].w;
                Pre[to] = i;
                if(!vis[to]) q.push(to), vis[to] = 1;
            }
        }
    }
    return dis[T] > 0;
}
int F() {
    int nowflow = INF;
    for(int i = T; i != S; i = E[Pre[i]].u) nowflow = min(nowflow, E[Pre[i]].f);
    for(int i = T; i != S; i = E[Pre[i]].u) E[Pre[i]].f -= nowflow, E[Pre[i] ^ 1].f += nowflow;
    anscost += dis[T] * nowflow;
}
int MCMF() {
    anscost = 0;
    while(SPFA()) 
        F();
    return anscost;
}
int be[21][21], tot = 0, X;
void Solve1() {
    memset(head, -1, sizeof(head)); num = 0;
    for(int i = 1; i < N; i++) {
        for(int j = 1; j <= M + i - 1; j++) {
            AddEdge(be[i][j], be[i][j] + X, a[i][j], 1);
            AddEdge(be[i][j] + X, be[i + 1][j], 0, 1);
            AddEdge(be[i][j] + X, be[i + 1][j + 1], 0, 1);
        }
    }
    for(int i = 1; i <= M; i++) AddEdge(S, be[1][i], 0, 1);
    for(int i = 1; i <= N + M - 1; i++) 
        AddEdge(be[N][i], be[N][i] + X, a[N][i], 1),
        AddEdge(be[N][i] + X, T, 0, 1);
    printf("%d\n", MCMF());
}
void Solve2() {
    memset(head, -1, sizeof(head)); num = 0;
    for(int i = 1; i < N; i++) {
        for(int j = 1; j <= M + i - 1; j++) {
            AddEdge(be[i][j], be[i + 1][j + 1], a[i][j], 1);
            AddEdge(be[i][j], be[i + 1][j], a[i][j], 1);
        }
    }
    for(int i = 1; i <= M; i++) AddEdge(S, be[1][i], 0, 1);
    for(int i = 1; i <= N + M - 1; i++) AddEdge(be[N][i], T, a[N][i], INF);
    printf("%d\n", MCMF()); 
}
void Solve3() {
    memset(head, -1, sizeof(head)); num = 0;
    for(int i = 1; i < N; i++)
        for(int j = 1; j <= M + i - 1; j++) {
            AddEdge(be[i][j], be[i + 1][j + 1], a[i][j], INF);
            AddEdge(be[i][j], be[i + 1][j], a[i][j], INF);
        }
    for(int i = 1; i <= M; i++) AddEdge(S, be[1][i], 0, 1);
    for(int i = 1; i <= N + M - 1; i++) AddEdge(be[N][i], T, a[N][i], INF);
    printf("%d\n", MCMF());
}
int main() {
    memset(head, -1, sizeof(head));
    M = read(); N = read(); X = (N + M - 1) * N;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M + i - 1; j++)
            a[i][j] = read(), be[i][j] = ++tot;
    Solve1();
    Solve2();
    Solve3();
    return 0;
}
/*

*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ4773: 负环(倍增Floyd)

一个很显然的思路(然而我想不到是用\(f[k][i][j]\)表示从\(i\)号点出发,走\(k\)步到\(j\)的最小值

14230
来自专栏hanlp学习笔记

hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

18200
来自专栏人工智能LeadAI

Python 中argparse模块的使用

如果脚本很简单或临时使用,没有多个复杂的参数选项,可以直接利用sys.argv将脚本后的参数依次读取(读进来的默认是字符串格式)。

10940
来自专栏数据处理

proc-tabulate

12520
来自专栏图形学与OpenGL

5.5 Opengl编程实例-红蓝三角形

22520
来自专栏机器学习从入门到成神

字符串面试题(一)— 字符串逆序

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

36310
来自专栏python爬虫实战之路

使用bloomfilter修改scrapy-redis去重

这篇文章憋的太久了,断断续续战线拉了好长。这个也是属于喜马拉雅那个项目的一部分,还要再忙一阵子。请大家见谅。

24820
来自专栏nummy

Uninformed search Python实现【译】

图的搜索可以分为uninformed搜索和informed搜索,两者的区别是前者是的搜索是盲目的,它不知道目标节点在哪,而后者是启发式的搜索。

16120
来自专栏tkokof 的技术,小趣及杂念

HGE系列之五 管中窥豹(基础类别)

继上次我们编写了那个小程序之后,想必大家对于HGE的认识都有了进一步的提高,那么现在,我想则是时候来一番“管中窥豹”,睹一睹HGE的源码实现了 :)而相应的源...

11110
来自专栏V站

Python科学计算:在Numpy的边缘试探(入门学习)

22160

扫码关注云+社区

领取腾讯云代金券