洛谷P4013 數字梯形問題(費用流)

題意

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

問在三個規則下怎麼取使得權值最大

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 + 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;
}
/*

*/