P4014 分配问题 【网络流24题 最小/大费用最大流】

传送门

废话：应该是一道最大流最小费用流的模板题

解题思路：在保证每个人都有工作的条件下获得的收益最大和最小。收益最小：费用流模板。收益最大：将收益取反，跑一遍板子，答案就等于最小费用取反。
一个超级源点 - > 每一个人 (流上限均为1,费用为0)
人->工作 (流上限为1，费用（最小收益为 Cij，最大收益为 -Cij ))
工作->超级汇点(流上限为1，费用为0)

代码：

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>

#define MT(a, b) memset(a,b,sizeof(a)
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
const double pai = acos(-1.0);
const double E = 2.718281828459;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double esp = 1e-6;
const int maxn = 5e2 + 5;

int n, Sta, End;
int inque[maxn], dis[maxn], pre[maxn], flow[maxn];
int maps[105][105];
struct node {
    int e, c, f, p;
} load[maxn * 100];
int head[maxn], sign;

void add_edge(int s, int e, int c, int f) {
    load[++sign] = node{e, c, f, head[s]};
    head[s] = sign;
}

bool spfa() {
    for (int i = 0; i <= n * 2 + 1; i++) {
        inque[i] = 0;
        flow[i] = dis[i] = INF;
        pre[i] = -1;
    }
    inque[Sta] = 1, dis[Sta] = 0;
    queue<int> q;
    q.push(Sta);
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        inque[s] = 0;
        for (int i = head[s], e, c, f; ~i; i = load[i].p) {
            e = load[i].e, c = load[i].c, f = load[i].f;
            if (f > 0 && dis[e] > dis[s] + c) {
                dis[e] = dis[s] + c;
                flow[e] = min(flow[s], f);
                pre[e] = i;
                if (!inque[e]) {
                    inque[e] = 1;
                    q.push(e);
                }
            }
        }
    }
    return dis[End] != INF;
}

void init() {
    sign = -1;
    memset(head, -1, sizeof(head));
}

int main() {
    init();
    int  minans = 0, maxans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            scanf("%d", &maps[i][j]);
    }

    Sta = 0, End = n * 2 + 1;
    ///求最小收入
    for (int i = 1; i <= n; i++) {
        add_edge(0, i, 0, 1);
        add_edge(i, 0, 0, 0);
        for (int j = 1; j <= n; j++) {
            add_edge(i, n + j, maps[i][j], 1);
            add_edge(n + j, i, -maps[i][j], 0);
        }
        add_edge(n + i, End, 0, 1);
        add_edge(End, n + i, 0, 0);
    }
    while (spfa()) {
        int f = flow[End];
        for (int i = pre[End]; i!=-1; i = pre[load[i ^ 1].e]) {
            minans += f * load[i].c;
            load[i].f -= f;
            load[i ^ 1].f += f;
        }
    }
    ///最大收入
    init();
    for (int i = 1; i <= n; i++) {
        add_edge(0, i, 0, 1);
        add_edge(i, 0, 0, 0);
        for (int j = 1; j <= n; j++) {
            add_edge(i, n + j, -maps[i][j] ,1);
            add_edge(n + j, i, maps[i][j] ,0);
        }
    }
    for (int j = 1; j <= n; j++) {
        add_edge(n + j, End, 0, 1);
        add_edge(End, n + j, 0, 0);
    }
    while (spfa()) {
        int f = flow[End];
        for (int i = pre[End]; i!=-1; i = pre[load[i ^ 1].e]) {
            maxans += f * load[i].c;
            load[i].f -= f;
            load[i ^ 1].f += f;
        }
    }
    printf("%d\n%d\n", minans, -maxans);
}