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

时间：2022-06-12 08:28:16

题意

$N$行的矩阵，第一行有$M$个元素，第$i$行有$M + i - 1$个元素

问在三个规则下怎么取使得权值最大

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

Sol

我只会第一问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$出发的)

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN = 1e5 + , INF = 1e9 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = ; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, M, S = , T = 1e5 + ;

int a[][];

struct Edge {

    int u, v, w, f, nxt;

}E[MAXN];

int head[MAXN << ], num = ;

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, );

}

int anscost, dis[MAXN], vis[MAXN], Pre[MAXN];

bool SPFA() {

    memset(dis, -0x3f, sizeof(dis));

    memset(vis, , sizeof(vis));

    queue<int> q; q.push(S); dis[S] = ;

    while(!q.empty()) {

        int p = q.front(); q.pop(); vis[p] = ;

        for(int i = head[p]; i !=- ; i = E[i].nxt) {

            int to = E[i].v;

            if((dis[to] < dis[p] + E[i].w) && E[i].f > ) {

                dis[to] = dis[p] + E[i].w;

                Pre[to] = i;

                if(!vis[to]) q.push(to), vis[to] = ;

            }

        }

    }

    return dis[T] > ;

}

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] ^ ].f += nowflow;

    anscost += dis[T] * nowflow;

}

int MCMF() {

    anscost = ;

    while(SPFA())

        F();

    return anscost;

}

int be[][], tot = , X;

void Solve1() {

    memset(head, -, sizeof(head)); num = ;

    for(int i = ; i < N; i++) {

        for(int j = ; j <= M + i - ; j++) {

            AddEdge(be[i][j], be[i][j] + X, a[i][j], );

            AddEdge(be[i][j] + X, be[i + ][j], , );

            AddEdge(be[i][j] + X, be[i + ][j + ], , );

        }

    }

    for(int i = ; i <= M; i++) AddEdge(S, be[][i], , );

    for(int i = ; i <= N + M - ; i++)

        AddEdge(be[N][i], be[N][i] + X, a[N][i], ),

        AddEdge(be[N][i] + X, T, , );

    printf("%d\n", MCMF());

}

void Solve2() {

    memset(head, -, sizeof(head)); num = ;

    for(int i = ; i < N; i++) {

        for(int j = ; j <= M + i - ; j++) {

            AddEdge(be[i][j], be[i + ][j + ], a[i][j], );

            AddEdge(be[i][j], be[i + ][j], a[i][j], );

        }

    }

    for(int i = ; i <= M; i++) AddEdge(S, be[][i], , );

    for(int i = ; i <= N + M - ; i++) AddEdge(be[N][i], T, a[N][i], INF);

    printf("%d\n", MCMF());

}

void Solve3() {

    memset(head, -, sizeof(head)); num = ;

    for(int i = ; i < N; i++)

        for(int j = ; j <= M + i - ; j++) {

            AddEdge(be[i][j], be[i + ][j + ], a[i][j], INF);

            AddEdge(be[i][j], be[i + ][j], a[i][j], INF);

        }

    for(int i = ; i <= M; i++) AddEdge(S, be[][i], , );

    for(int i = ; i <= N + M - ; i++) AddEdge(be[N][i], T, a[N][i], INF);

    printf("%d\n", MCMF());

}

int main() {

    memset(head, -, sizeof(head));

    M = read(); N = read(); X = (N + M - ) * N;

    for(int i = ; i <= N; i++)

        for(int j = ; j <= M + i - ; j++)

            a[i][j] = read(), be[i][j] = ++tot;

    Solve1();

    Solve2();

    Solve3();

    return ;

}

/*

*/

　　

相关文章