luogu P4013 数字梯形问题

三倍经验，三个条件，分别对应了常见的3种模型，第一种是限制每个点只能一次且无交点，我们可以把这个点拆成一个出点一个入点，capacity为1，这样就限制了只选择一次，第二种是可以有交点，但不能有交边，那我们就不需要拆点，限制每条capacity都为1就可以了，第三种直接连，没有限制(

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x)&(-x))

typedef long long LL;

const int maxm = 1e6+;

const int INF = 0x3f3f3f3f;

struct edge{

    int u, v, cap, flow, cost, nex;

} edges[maxm];

int head[maxm], cur[maxm], cnt, fa[maxm], d[maxm], buf[][], num[][], ID;

bool inq[maxm];

void init() {

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

}

void add(int u, int v, int cap, int cost) {

    edges[cnt] = edge{u, v, cap, , cost, head[u]};

    head[u] = cnt++;

}

void addedge(int u, int v, int cap, int cost) {

    add(u, v, cap, cost), add(v, u, , -cost);

}

bool spfa(int s, int t, int &flow, LL &cost) {

    //for(int i = 0; i <= n+1; ++i) d[i] = INF; //init()

    memset(d, , sizeof(d));

    memset(inq, false, sizeof(inq));

    d[s] = , inq[s] = true;

    fa[s] = -, cur[s] = INF;

    queue<int> q;

    q.push(s);

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        inq[u] = false;

        for(int i = head[u]; i != -; i = edges[i].nex) {

            edge& now = edges[i];

            int v = now.v;

            if(now.cap > now.flow && d[v] > d[u] + now.cost) {

                d[v] = d[u] + now.cost;

                fa[v] = i;

                cur[v] = min(cur[u], now.cap - now.flow);

                if(!inq[v]) {q.push(v); inq[v] = true;}

            }

        }

    }

    if(d[t] == INF) return false;

    flow += cur[t];

    cost += 1LL*d[t]*cur[t];

    for(int u = t; u != s; u = edges[fa[u]].u) {

        edges[fa[u]].flow += cur[t];

        edges[fa[u]^].flow -= cur[t];

    }

    return true;

}

int MincostMaxflow(int s, int t, LL &cost) {

    cost = ;

    int flow = ;

    while(spfa(s, t, flow, cost));

    return flow;

}

void run_case() {

    int m, n; cin >> m >> n;

    int s = , t = 1e6;

    // first

    init();

    for(int i = m; i < n+m; ++i)

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

            num[i][j] = ++ID;

            cin >> buf[i][j];

            addedge(ID<<, (ID<<)|, , -buf[i][j]);

        }

    for(int i = m; i < n+m-; ++i) {

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

            addedge((num[i][j]<<)|, num[i+][j]<<, , );

            addedge((num[i][j]<<)|, num[i+][j+]<<, , );

        }

    }

    for(int i = ; i <= m; ++i) addedge(s, num[m][i]<<, , );

    for(int i = ; i < n+m; ++i) addedge((num[n+m-][i]<<)|, t, , );

    LL cost = ;

    MincostMaxflow(s, t, cost);

    cout << -cost << "\n";

    // second

    init();

    for(int i = m; i < n+m-; ++i)

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

            addedge(num[i][j], num[i+][j], , -buf[i+][j]);

            addedge(num[i][j], num[i+][j+], , -buf[i+][j+]);

        }

    for(int i = ; i <= m; ++i) addedge(s, num[m][i], , -buf[m][i]);

    for(int i = ; i < n+m; ++i) addedge(num[n+m-][i], t, INF, );

    cost = , MincostMaxflow(s, t, cost);

    cout << -cost << "\n";

    // third

    init();

    for(int i = m; i < n+m-; ++i)

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

            addedge(num[i][j], num[i+][j], INF, -buf[i+][j]);

            addedge(num[i][j], num[i+][j+], INF, -buf[i+][j+]);

        }

    for(int i = ; i <= m; ++i) addedge(s, num[m][i], , -buf[m][i]);

    for(int i = ; i < n+m; ++i) addedge(num[n+m-][i], t, INF, );

    cost = , MincostMaxflow(s, t, cost);

    cout << -cost << "\n";

}

int main() {

    ios::sync_with_stdio(false), cin.tie();

    run_case();

    cout.flush();

    return ;

}