【問題解】ネットワークストリーム24問題の割り当て問題

トランスファゲート
構想の剖析
割り当ての問題は、人と仕事を別々にマッチングすることですが、一般的な二分図マッチングとは異なり、各マッチングには重みがあります.この問題は二分図の最大重みの完璧なマッチング問題である.
グラフィックスモデリング
この問題は二分図の最大重みが完璧に一致する専門アルゴリズムKMアルゴリズムで解決できるが,ここではネットワークフロー解法のみを述べる.まず,人と仕事の下付き文字はいずれも1~nであり,直接図を建てると曖昧になることが分かったので,人の下付き文字は1~nであり,仕事の下付き文字はn+1~2 nであると定義できる.i番目のi個人がj番目のjの仕事をすると生じる利益はCi,j C i,j(i,j≦n i,j≦n)であり,iからn+j n+jへ1本の容量が1であり,費用がcの1本の辺に相当し,最後に(最初に)ソース点s sと送金点tを確立し,sから1~nと下付きのすべてのノードに1本の容量が1であり,費用が0の辺に1本の容量があり,同様に,n+1~2 nと表記されたすべてのノードからt連に容量1,費用0の辺からs sからtまで最小費用最大流を走ればよいが,求めた最小費用は第1問の答えであり,第2問に対して最大収益を求めるにはどうすればよいのか.実際には、一度図を再構築し、容量を元の容量の逆数にして、最小費用の最大ストリームをもう一度走って、求めた最小費用を逆数にするのが2番目の質問の答えだと思います.
code c o d e

#include
#include
#include
#include
#include
#include
#define min(x, y) ((x) < (y) ? (x) : (y))
int a[101][101];
struct Graph {
    static const int infty = 0x7f7f7f7f;
    struct edgetype {
        int to, next, flow, cap, cost;
    };
    int n, m, s, t;
    std::vector< edgetype > edge;
    std::vector< bool > inQ;
    std::vector< int > head, dist, path;
    std::queue< int > Q;
    Graph() {
        n = m = 0;
        head.clear(); dist.clear(); edge.clear(); inQ.clear(); path.clear(); 
    }
    Graph(int n, int m) {
        this->n = n; this->m = m;
        head.resize(n + 1); dist.resize(n + 1); inQ.resize(n + 1); path.resize(n + 1); 
        head.assign(n + 1, -1);
    }
    void AddEdge(int from, int to, int cap, int cost) {
        edge.push_back((edgetype){to, head[from], 0, cap, cost});
        head[from] = edge.size() - 1;
        edge.push_back((edgetype){from, head[to], 0, 0, -cost});
        head[to] = edge.size() - 1;
    }
    bool FindPath() {
        dist.assign(n + 1, infty);
        inQ.assign(n + 1, false);
        path.assign(n + 1, -1);
        while (!Q.empty()) Q.pop();
        Q.push(s); dist[s] = 0; inQ[s] = true; 
        while (!Q.empty()) {
            int u = Q.front(); Q.pop(); inQ[u] = false;
            for (int i = head[u]; i != -1; i = edge[i].next) {
                int v = edge[i].to;
                if (edge[i].flow < edge[i].cap && dist[v] > dist[u] + edge[i].cost) {
                    dist[v] = dist[u] + edge[i].cost; path[v] = i; 
                    if (!inQ[v]) {
                        Q.push(v);
                        inQ[v] = true;
                    }
                }
            }
        }
        return path[t] != -1;
    }
    void Argument(long long& Mincost) {
        long long alpha = infty;
        for (int i = path[t]; i != -1; i = path[edge[i ^ 1].to]) 
            alpha = min(alpha, edge[i].cap - edge[i].flow);
        Mincost += dist[t] * alpha;
        for (int i = path[t]; i != -1; i = path[edge[i ^ 1].to]) {
            edge[i].flow += alpha;
            edge[i ^ 1].flow -= alpha;
        }
    }
    long long MincostMaxflow(int s, int t) {
        this->s = s; this->t = t;
        long long Mincost = 0;
        while (FindPath())
            Argument(Mincost);
        return Mincost;
    }
};
Graph G;

int main() {
    int n;
    scanf("%d", &n);
    G = Graph(2 * n + 2, n * n + 2 * n);
    for (int i = 1; i <= n; i++) {
        G.AddEdge(0, i, 1, 0);
        G.AddEdge(n + i, n * 2 + 1, 1, 0);
    }
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            G.AddEdge(i, n + j, 1, a[i][j]);
        }
    printf("%lld
", G.MincostMaxflow(0, 2 * n + 1));
    G = Graph(2 * n + 2, n * n + 2 * n);;
    for (int i = 1; i <= n; i++) {
        G.AddEdge(0, i, 1, 0);
        G.AddEdge(n + i, n * 2 + 1, 1, 0);
    }
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            G.AddEdge(i, n + j, 1, -a[i][j]);
    printf("%lld
", -G.MincostMaxflow(0, 2 * n + 1));
    return 0;
}