[BOJ 1031] 스타 대결

문제 출처 : https://www.acmicpc.net/problem/1031

 

풀이 :

Maximum Flow 문제입니다.

 

아래의 조건에 따라 푸시면 됩니다.

1. A팀의 경기수 총합 != B팀의 경기수 총합  => -1

2. A팀의 경기수 총합 != Maximum Flow      => -1

3. A팀의 경기수 총합 == Maximum Flow     => 사전순 정렬

 

이문제의 핵심은 3번 사전순 정렬인데

사전순 정렬은 엣지 하나를 고르고 엣지와 동일한 시작점에서 동일한 끝점으로 갈수있는 다른 플로우가 있는지 찾은 후 있으면 엣지의 플로우를 지워주고 경로에 Flow를 흘려주시면 됩니다.

단 찾을때 정렬을 해야하기 때문에 시작점과 끝점의 범위에 주의해야합니다.

 

만약 인풋이

2 2

1 1

1 1

일때,

1->3, 2->4에 Flow가 흐른 상태라면

아래와 같은 과정을 통해 사이클을 찾아 정렬을 할 수 있습니다.

 

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define ms 102
typedef pair<int, int> p;
 
struct MF {
    struct edge {
        int to, c, f;
        edge* d;
        edge(int to1 = -1, int c1 = 0) :to(to1), c(c1), f(0), d(nullptr) {}
        int spare() { return c - f; }
        void addFlow(int f1) {
            f += f1;
            d->f -= f1;
        }
    };
 
    int S, E, mf = 0, n, m, a, map[51][51], limitA = 0, limitB = 0;
    vector<edge*>adj[ms];
 
    void init() {
        for (int i = 0; i < ms; i++)adj[i].clear();
        for (int i = 0; i < 51; i++)for (int j = 0; j < 51; j++)map[i][j] = 0;
        mf = 0;
    }
 
    void addEdge(int u, int v, int c) {
        edge* e1 = new edge(v, c), * e2 = new edge(u, 0);
        e1->d = e2;
        e2->d = e1;
        adj[u].push_back(e1);
        adj[v].push_back(e2);
    }
 
    void solve() {
        while (1) {
            int pre[ms];
            for (int i = 0; i < ms; i++)pre[i] = -1;
            edge* path[ms] = { 0 };
            queue<int> q;
            q.push(S);
            while (!q.empty()) {
                int now = q.front();
                q.pop();
                for (edge* e : adj[now]) {
                    int next = e->to;
                    if (pre[next] == -1 && e->spare() > 0) {
                        pre[next] = now;
                        path[next] = e;
                        q.push(next);
                        if (next == E)break;
                    }
                }
            }
            if (pre[E] == -1)break;
            for (int i = E; i != S; i = pre[i]) path[i]->addFlow(1);
            mf++;
        }
        if (mf != limitA) {
            cout << -1;
            return;
        }
        for (edge* e : adj[S])
        {
            for (edge* e1 : adj[e->to])
            {
                if (e1->to == S)continue;
                if (e1->f == 0)continue;
                int pre[ms];
                for (int i = 0; i < ms; i++)pre[i] = -1;
                edge* path[ms] = { 0 };
                queue<int> q;
                q.push(e->to);
                while (!q.empty()) {
                    int now = q.front();
                    q.pop();
                    for (edge* e2 : adj[now]) {
                        int next = e2->to;
                        if (now < e->to || now == e->to && next < e1->to)continue;
                        if (pre[next] == -1 && e2->spare() > 0) {
                            pre[next] = now;
                            path[next] = e2;
                            q.push(next);
                            if (next == e1->to)break;
                        }
                    }
                }
                if (pre[e1->to] == -1)continue;
                e1->f = e1->d->f = 0;
                for (int i = e1->to; i != e->to; i = pre[i]) path[i]->addFlow(1);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (edge* e : adj[i]) {
                if (e->to == 0)continue;
                map[i][e->to - n] = e->f;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cout << map[i][j];
            }
            cout << '\n';
        }
    }
 
    void inp() {
        cin >> n >> m;
        S = 0, E = ms - 1;
        for (int i = 1; i <= n; i++) {
            cin >> a;
            limitA += a;
            addEdge(S, i, a);
        }
        for (int i = 1; i <= m; i++) {
            cin >> a;
            limitB += a;
            addEdge(i + n, E, a);
        }
        if (limitA != limitB) {
            cout << -1;
            return;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = n + 1; j <= n + m; j++)addEdge(i, j, 1);
        }
        solve();
    }
};
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    MF m;
    m.init();
    m.inp();
}