나는 talALGO 팀의 ploffer11 이다.

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

3666이 대표적인 예인데,

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

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

Condition

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

Example

‌  

1

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

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

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

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

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

그러므로 다 옮긴 후에는

‌                                    

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';
    }
}