人生第一道24题，纪念一下qaq

Description

给定一张半完全有向二分图(每个左边节点都有边指向每个右边节点)，左右两边节点数分别为$m,n$.

左边节点$i$有货物$a_i$, 右边节点$j$有需求$b_j$, 满足供需平衡$\sum a_i = \sum b_j$.

对于一条从$i$指向$j$的边，其费用为$cost_{i,j}$. 求让右边所有需求被满足的方案的最小费用.

$1 \leq n,m \leq 100$.

Samples

Sample Input #1

2 3
220 280
170 120 210
77 39 105
150 186 122

Sample Output #1

1 2	48500 69140

Solution

首先膜拜$\texttt {Network Flow Master}$ xht, 神仙10min爆切NOI网络流题太强大了。

明显抽象成图之后这种有限制的最短路可以用网络流来解决。

因为有多个起点，那么考虑建立超级源点，超级汇点。

然后把超源和左边连上流量为$a_i$, 费用为$0$的边，超汇和右边连上流量为$b_i$, 费用为$0$的边。

最后$n^2$的把原二分图的每条边连好，流量为$inf$, 费用为$cost_{i,j}$.

结果跑个费用流就完事了，最大费用就建负费用图再跑一遍（（（（

Code

/* Headers */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define RevEdge(x) x^1
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO {
#define gc() (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
    const int SIZ = 1 << 21 | 1;
    char* iS, * iT, ibuff[SIZ], obuff[SIZ], * oS = obuff, * oT = oS + SIZ - 1, fu[110], cc;
    int fr;
    inline void out() {
        fwrite(obuff, 1, oS - obuff, stdout);
        oS = obuff;
    }
    template<class Type>
    inline void read(Type& x) {
        x = 0;
        Type y = 1;
        for (cc = gc(); (cc > '9' || cc < '0') && cc != '-'; cc = gc());
        cc == '-' ? y = -1 : x = (cc & 15);
        for (cc = gc(); cc >= '0' && cc <= '9'; cc = gc())
            x = x * 10 + (cc & 15);
        x *= y;
    }
    template<class Type>
    inline void print(Type x, char text = '\n') {
        if (x < 0)
            * oS++ = '-', x *= -1;
        if (x == 0)
            * oS++ = '0';
        while (x)
            fu[++fr] = x % 10 + '0', x /= 10;
        while (fr)
            * oS++ = fu[fr--];
        * oS++ = text;
        out();
    }
    inline void prints(char x[], char text = '\n') {
        for (register int i = 0; x[i]; ++i)
            * oS++ = x[i];
        * oS++ = text;
        out();
    }
}
using namespace FastIO;
template<typename T>
inline T max(T a, T b) {return (a > b) ? a : b;}
template<typename T>
inline T min(T a, T b) {return (a > b) ? b : a;}
/* definitions */
#define ll long long
const int MAXN = 2e2 + 10, MAXM = 2e4 + 10;
const int inf = 0x7f7f7f7f;
struct Edge {int next, to, wgh, cst;} Graph[MAXM];
int n, m, s, t, dist[MAXN], cur[MAXN], head[MAXN], cnt = 1;
int a[MAXN], b[MAXN], cost[MAXN][MAXN];
bool visited[MAXN];
/* functions */
inline void Add_Edge(int from, int to, int wgh, int cst) {
    Graph[++cnt] = (Edge) {head[from], to, wgh, cst};
    Graph[++cnt] = (Edge) {head[to], from, 0, -cst};
    head[from] = cnt - 1; head[to] = cnt;
}
inline void CLEAR() {
    memset(dist, 0, sizeof dist);
    memset(cur, 0, sizeof cur);
    memset(head, 0, sizeof head);
    memset(visited, 0, sizeof visited);
    memset(Graph, 0, sizeof Graph); cnt = 1;
}
namespace DINIC {
    inline bool SPFA(int s, int t) {
        memset(dist, 0x7f, sizeof dist);
        memcpy(cur, head, sizeof head); std::queue<int> Q;
        Q.push(s); dist[s] = 0; visited[s] = true;
        while(!Q.empty()) {
            int u = Q.front(); Q.pop(); visited[u] = false;
            for(int i = head[u]; i; i = Graph[i].next) {
                int v = Graph[i].to, w = Graph[i].cst;
                if(Graph[i].wgh && dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    if(!visited[v]) Q.push(v), visited[v] = true;
                 }
            }
        } return dist[t] < inf;
    }
    inline int DFS(int u, int t, int Maxflow) {
        if(u == t) return Maxflow;
        visited[u] = true; int res = 0;
        for(int &i = cur[u]; i && res < Maxflow; i = Graph[i].next) {
            int v = Graph[i].to, w = Graph[i].cst;
            if(Graph[i].wgh && !visited[v] && dist[v] == dist[u] + w) {
                int flow = DFS(v, t, min(Graph[i].wgh, Maxflow));
                if(flow) {
                    Graph[i].wgh -= flow; Graph[i ^ 1].wgh += flow;
                    Maxflow -= flow; res += flow;
                }
            }
        } visited[u] = false; return res;
    }
    inline ll dinic(int s, int t) {
        ll res = 0;
        while(SPFA(s, t)) {
            ll flow;
            while((flow = DFS(s, t, inf))) res += 1ll * flow * dist[t];
        } return res;
    }
}
int main(int argc, char *argv[]) {
    /*FILE_IN("data.in");*/ read(m); read(n); t = m + n + 1;
    FOR(i, 1, m, 1) read(a[i]); FOR(i, 1, n, 1) read(b[i]);
    FOR(i, 1, m, 1) FOR(j, 1, n, 1) read(cost[i][j]);
    FOR(i, 1, m, 1) Add_Edge(s, i, a[i], 0);
    FOR(i, 1, n, 1) Add_Edge(m + i, t, b[i], 0);
    FOR(i, 1, m, 1) FOR(j, 1, n, 1) Add_Edge(i, m + j, inf, cost[i][j]);
    ll mincost = DINIC::dinic(s, t); CLEAR();
    FOR(i, 1, m, 1) Add_Edge(s, i, a[i], 0);
    FOR(i, 1, n, 1) Add_Edge(m + i, t, b[i], 0);
    FOR(i, 1, m, 1) FOR(j, 1, n, 1) Add_Edge(i, m + j, inf, -cost[i][j]);
    ll maxcost = DINIC::dinic(s, t);
    printf("%lld\n%lld", mincost, -maxcost);
    return 0;
}

LuoguP4015「网络流24题」题解