BOJ 3666 리스크 풀이

나는 talALGO 팀의 ploffer11 이다.

Network Flow 문제들을 풀다 보면 자연스럽게 풀이가 없는 문제들도 풀게 되는 경우가 종종 있다.

3666이 대표적인 예인데,

일단 이 문제, 디스크립션부터 조금 애매하다.

조건부터 제대로 정리하고 넘어가겠다.

Condition

1. 주둔하는 군대는 0이 될 수 없다.
2. 각 군대는 최대 한 칸 움직일 수 있다.
3. 인접한 노드에 적이 있는 노드들의 군대 주둔수의 최소를 최대로 만드는 문제이다.

Example

‌  

빨간색 노드가 적이 있는 노드이고, 초록색 노드가 그와 인접한 노드이다.

2번 노드의 군대 3개를 4에 2개, 3에 1개를 보낸다.

이 때, 2번 노드의 군대 주둔 수가 0이 되는데, 적당히 1에서 끌어오면 된다.

근데 1에 7이나 있으니 6정도 가져와서 3번 노드와 4번노드에 줘도 되지 않을까?

이는 조건2에 위배되므로 불가능하다.

그러므로 다 옮긴 후에는

‌                                    

이런 모양이 되고, 답은 4가 된다.

Solution

이 문제의 모델링은 다음과 같다.

이후 빨간색 간선에 대해 파라메트릭 서치를 진행하면 된다.

모델링에 대해 간단히 설명하자면, 각 노드가 최대 처음 군대 주둔수만큼 유량을 흘려도 된다는 사실은 자명하다. 그러므로 정점분할 후 군대 주둔수로 이을 수 있다.

그리고 인접한 노드에 적이 없는 노드들은 결국에는 1의 군대는 자기 노드에 남아 있어야하므로 소스에서 이을 때 1을 빼준다. 물론 인접한 노드에 적이 있다면 그럴 필요가 없다.

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 987654321;
const int MOD = 1e9 + 7;

class Dinic
{
private:
    struct Edge
    {
        int to, rev, cap, flow;
        Edge(int _to, int _cap) : to(_to), cap(_cap), flow(0) {}
    };

    vector<vector<Edge>> adj;
    vector<int> depth, work;

    void bfs()
    {
        fill(depth.begin(), depth.end(), -1);

        queue<int> q;
        q.push(source);
        depth[source] = 0;

        while (!q.empty())
        {
            int s = q.front();
            q.pop();

            for (auto &e : adj[s])
            {
                if (e.cap - e.flow > 0 && depth[e.to] == -1)
                {
                    depth[e.to] = depth[s] + 1;
                    q.push(e.to);
                }
            }
        }
    }

    int dfs(int s, int flow)
    {
        if (s == sink)
            return flow;

        for (int i = work[s]; i < adj[s].size(); i++, work[s]++)
        {
            auto &e = adj[s][i];

            if (depth[e.to] > depth[s] && e.cap - e.flow > 0)
            {
                int f = dfs(e.to, min(flow, e.cap - e.flow));

                if (f < 0)
                    continue;

                e.flow += f;
                adj[e.to][e.rev].flow -= f;

                return f;
            }
        }

        return -1;
    }

public:
    int source, sink;

    Dinic(int n)
    {
        source = 0;
        sink = n + 1;

        adj.resize(sink + 1);
        depth.resize(sink + 1);
        work.resize(sink + 1);
    }

    void add_edge(int u, int v, int cap)
    {
        adj[u].push_back(Edge(v, cap));
        adj[v].push_back(Edge(u, 0));
        adj[u].back().rev = adj[v].size() - 1;
        adj[v].back().rev = adj[u].size() - 1;
    }

    int max_flow()
    {
        int flow = 0;
        while (1)
        {
            bfs();
            if (depth[sink] == -1)
                break;

            fill(work.begin(), work.end(), 0);
            while (1)
            {
                int f = dfs(source, 987654321);
                if (f < 0)
                    break;
                flow += f;
            }
        }

        return flow;
    }
};

char board[105][105];
int army[105];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
    {
        vector<int> team, enemy;

        int n;
        cin >> n;

        for (int i = 1; i <= n; i++)
        {
            cin >> army[i];
        }

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin >> board[i][j];

        for (int i = 1; i <= n; i++)
        {
            if (army[i] == 0)
                continue;

            int flag = true;
            for (int j = 1; j <= n; j++)
                if (board[i][j] == 'Y' && army[j] == 0)
                    flag = false;
            //cout << "edge: " << flag << " " << i << '\n';
            (flag ? team : enemy).push_back(i);
        }

        int s = 0, e = 10000;
        while (s <= e)
        {
            Dinic MF(2 * n);
            int m = (s + e) / 2;
            int f = m * enemy.size();

            for (auto i : team)
            {
                MF.add_edge(MF.source, i, army[i] - 1);
                MF.add_edge(i, n + i, army[i]);
            }

            for (auto i : enemy)
            {
                MF.add_edge(i, MF.sink, m);
                MF.add_edge(MF.source, i, army[i]);
                MF.add_edge(i, n + i, army[i]);
            }

            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (board[i][j] == 'Y')
                        MF.add_edge(n + i, j, INF);

            int flow = MF.max_flow();
            //cout << m << " " << f << " " << flow << '\n';
            if (flow == f)
                s = m + 1;
            else
                e = m - 1;
        }
        cout << e << '\n';
    }
}