UVaOJ)11765 Component Placement

문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2865

N개의 정점이 있을 때 N개의 정점이 상단에 연결되어야 하는지 하단에 연결되어야 하는지 여부를 구해주어야 하는 문제이다.

각각 상단에 연결되었을 때와 하단에 연결되었을 때의 비용이 주어지며 

반드시 상단에 연결되어야 하는 경우, 반드시 하단에 연결되어야 하는 경우, 둘다 가능한 경우가 주어진다.

이 후 M개의 정보가 주어지는데 이 정보는 x 와 y 정점이 같은 곳(상단or 하단)에 연결되지 않았을 경우 생기는 추가비용이다.

이 때 모든 정점을 연결하였을 때 최소비용을 구하는 문제이다.

이 문제를 최소컷 문제로 변형해서 푼다고 생각을 하면

하나의 정점은 양쪽에 연결되어 있을것이고, 이 때 컷이 의미하는건 컷된 간선쪽을 선택하는것이다.

그리고 M개의 정보에 대한 처리는 x와 y에 가중치가 z인 간선을 연결해주는것으로 처리가 가능하다.

이렇게 할 경우 같은 곳을 선택하지 않았을 경우 반드시 서로 다른곳의 간선과 함께 두 정점 x y 사이의 간선을 같이 컷을 해줘야 상단과 하단이 분리가 되므로 추가비용을 강제할 수 있다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define INF 987654321
using namespace std;
struct networkflow {
    int n;
    struct Edge {
        int v, cap, rev;
        Edge(int v, int cap, int rev) :v(v), cap(cap), rev(rev) {}
    };
    vector<vector<Edge>> vt;
    void addEdge(int s, int e, int c) {
        vt[s].emplace_back(e, c, vt[e].size());
        vt[e].emplace_back(s, 0, vt[s].size() - 1);
    }
    vector<int> level, work;
    networkflow(int n) :n(n) {
        vt.resize(n + 1);
    }
    bool bfs(int src, int sink) {
        queue<int> qu;
        level.assign(n + 1, -1);
        level[src] = 0;
        qu.push(src);
        while (qu.size()) {
            int here = qu.front();
            qu.pop();
            for (auto next : vt[here]) {
                if (next.cap&&level[next.v] == -1) {
                    level[next.v] = level[here] + 1;
                    qu.push(next.v);
                }
            }
        }
        return level[sink] != -1;
    }
    int dfs(int here, int crtcap, int target) {
        if (here == target)return crtcap;
        for (int &i = work[here]; i < vt[here].size(); i++) {
            int next = vt[here][i].v;
            int cap = vt[here][i].cap;
            if (cap&&level[here] + 1 == level[next]) {
                int flow = dfs(next, min(crtcap, cap), target);
                if (flow) {
                    vt[here][i].cap -= flow;
                    vt[next][vt[here][i].rev].cap += flow;
                    return flow;
                }
            }
        }
        return 0;
    }
    int getmaxflow(int src, int sink) {
        int ret = 0;
        while (bfs(src,sink)) {
            work.assign(n + 1, 0);
            while (1) {
                int flow = dfs(src, INF, sink);
                if (!flow)break;
                ret += flow;
            }
        }
        return ret;
    }
};
int t, n, m, x, y, z, a[222], b[222];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        networkflow nf(n + 2);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &b[i]);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            if (x == 1) {
                nf.addEdge(n + 1, i, a[i]);
                nf.addEdge(i, n + 2, INF);
            }
            else if (x == -1) {
                nf.addEdge(n + 1, i, INF);
                nf.addEdge(i, n + 2, b[i]);
            }
            else {
                nf.addEdge(n + 1, i, a[i]);
                nf.addEdge(i, n + 2, b[i]);
            }
        }
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &x, &y, &z);
            nf.addEdge(x, y, z);
            nf.addEdge(y, x, z);
        }
        printf("%d\n", nf.getmaxflow(n + 1, n + 2));
    }
    return 0;
}