uva12264 Risk

最小值最大，就二分判断。

map[i] = '0'+map[i];这样更方便

每个点拆成i，i’,  S连i，cap为a[i]，i’连T，cap为1(保证至少剩一个）或mid。

i,i’ ，a[i]

i->j’,   inf    //把i连到j就WA了...所以题目的意思大概是只能移动到相邻点?

判断一下border

#include<iostream>

#include<queue>

#include<cmath>

#include<cstring>

#include<vector>

#include<algorithm>

#include<string>

using namespace std;

const int maxn = , INF = 0x3f3f3f3f;

int a[maxn], border[maxn];

string map[maxn];

struct Edge

{

    int from, to, cap, flow;

    Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f) {}

};

struct EdmondsKarp

{

    int n, m;

    vector<Edge> edges;

    vector<int> G[maxn];

    int a[maxn];

    int p[maxn];

    void init(int n)

    {

        this->n = n;

        for (int i = ; i < n; i++)

        {

            G[i].clear();

        }

        edges.clear();

        memset(p, , sizeof(p));//²»ÐèÒª£¿

    }

    void AddEdge(int u, int v, int c)

    {

        edges.push_back(Edge(u, v, c, ));

        edges.push_back(Edge(v, u, , ));

        m = edges.size();

        G[u].push_back(m - );

        G[v].push_back(m - );

    }

    int MaxFlow(int s, int t)

    {

        int flow = ;

        for (;;)

        {

            memset(a, , sizeof(a));

            queue<int> Q;

            Q.push(s);

            a[s] = INF;

            while (!Q.empty())

            {

                int u = Q.front();

                Q.pop();

                for (int i = ; i < G[u].size(); i++)

                {

                    Edge& e = edges[G[u][i]];

                    if (!a[e.to] && e.cap > e.flow)

                    {

                        a[e.to] = min(a[u], e.cap - e.flow);

                        Q.push(e.to);

                        p[e.to] = G[u][i];

                    }

                }

                if (a[t])

                    break;

            }

            if (!a[t])

                break;

            for (int i = t; i != s; i = edges[p[i]].from)

            {

                edges[p[i]].flow += a[t];

                edges[p[i] ^ ].flow -= a[t];

            }

            flow += a[t];

        }

        return flow;

    }

}E;

int Build(int val,int N)

{

    for (int i = ; i <= N; i++)

    {

        if (!a[i])

            continue;

        E.AddEdge(, i, a[i]);

        E.AddEdge(i, i + N, a[i]);

        for (int j = ; j <= N; j++)

            if (map[i][j] == 'Y')

            {

                if (!a[j])

                    border[i] = true;         //border

                else

                    E.AddEdge(i, j + N, INF);

            }

    }

    int ans = ;

    for (int i = ; i <= N; i++)

        if (border[i])

        {

            E.AddEdge(i + N,  * N + , val);

            ans += val;

        }

        else if (a[i])

        {

            E.AddEdge(i + N,  * N + , );

            ans++;

        };

        return ans;

}

void solve(int n)

{

    int a, b, ans;

    int l = , r = ;

    while (l<r)

    {

        E.init( * n + );

        int mid = l+(r-l)/;

        a = Build(mid, n);

        b = E.MaxFlow(,  * n + );

        if (a == b)

        {

            l = mid + ;

            ans = mid;

        }

        else r = mid;

    }

    cout << ans << endl;

}

void input(int n){

        memset(a, , sizeof(a));

        memset(border, , sizeof(border));

        for (int i = ; i < maxn; i++)

            map[i].clear();

        for (int i = ; i <= n; i++)

            cin >> a[i];

        for (int i = ; i <= n; i++)

        {

            cin >> map[i];

            map[i] = ''+map[i];

        }

}

int main()

{

    int T;

    cin >> T;

    while (T--)

    {

        int n;

        cin >> n;

        input(n);

        solve(n);

    }

    return ;

}