uva 12264 Risk

https://vjudge.net/problem/UVA-12264

题意：

有很多个阵地，分为敌方和己方，每个士兵可以移动到相邻的己方的阵地，但是只能移动一步。
现在要让与敌方相邻的阵地中士兵最少的最多。

思路：

最少的最多，那显然二分。
二分这个最少的值。拆点，敌方阵地不管，S向己方阵地$i$向连边，容量为本阵地士兵的数量，$i‘$向T连边，如果是与敌方相邻的阵地，那么容量为二分的值；如果是处于己方阵地的包围，那么容量为1即可。最后跑最大流判断是否满流。

STD：

本STD在uva上AC，uvalive上WA，请谨慎食用。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 205;
int a[N];
char s[N][N];
bool is[N];

struct edge
{
    int u,v,cap;
    edge(int u,int v,int cap):u(u),v(v),cap(cap){}
    edge(){}
};

vector<edge> es;
vector<int> G[N];
int n,S,T;
int dis[N],cur[N];

void adde(int u,int v,int cap)
{
    es.push_back(edge(u,v,cap));
    es.push_back(edge(v,u,0));
    int sz = es.size();
    G[u].push_back(sz-2);
    G[v].push_back(sz-1);
}

bool bfs()
{
    memset(dis,inf,sizeof dis);
    dis[S] = 0;
    queue<int> q;
    q.push(S);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0;i < G[u].size();i++)
        {
            edge &e = es[G[u][i]];
            int v = e.v;
            if (e.cap > 0 && dis[v] >= inf)
            {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis[T] < inf;
}

int dfs(int u,int flow)
{
    if (u == T) return flow;
    for (int i = cur[u];i < G[u].size();i++)
    {
        cur[u] = i;
        edge &e = es[G[u][i]];
        int v = e.v;
        if (dis[v] == dis[u] + 1 && e.cap > 0)
        {
            int tmp = dfs(v,min(e.cap,flow));
            if (tmp)
            {
                e.cap -= tmp;
                es[G[u][i]^1].cap += tmp;
                return tmp;
            }
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0;
    while (bfs())
    {
        int tmp;
        memset(cur,0,sizeof(cur));
        while (tmp = dfs(S,inf)) ans += tmp;
    }
    return ans;
}

bool meet(int lim)
{
    for (int i = 0;i < N;i++) G[i].clear();
    es.clear();
    for (int i = 1;i <= n;i++)
    {
        if (a[i] <= 0) continue;
        adde(S,i,a[i]);
        adde(i,i+n,inf);
    }
    int sum = 0;
    for (int i = 1;i <= n;i++)
    {
        if (a[i] <= 0) continue;
        if (is[i])
        {
            sum += lim;
            adde(i+n,T,lim);
        }
        else
        {
            sum++;
            adde(i+n,T,1);
        }
    }
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= n;j++)
        {
            if (i == j) continue;
            if (a[i] <= 0 || a[j] <= 0) continue;
            if (s[i][j] == 'Y')
            {
                adde(i,j+n,inf);
            }
        }
    }
    int ans = dinic();
    return ans >= sum;
}

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        memset(is,0,sizeof is);
        scanf("%d",&n);
        S = 0;
        T = 2 * n + 1;
        for (int i = 1;i <= n;i++)
        {
            scanf("%d",&a[i]);
        }
        for (int i = 1;i <= n;i++)
        {
            scanf("%s",s[i]+1);
        }
        for (int i = 1;i <= n;i++)
        {
            for (int j = 1;j <= n;j++)
            {
                if (a[i] > 0 && a[j] <= 0)
                {
                    if (s[i][j] == 'Y') is[i] = true;
                }
            }
        }
        int l = 1,r = 1e5;
        while (r - l > 1)
        {
            int mid = (l + r) >> 1;
            if (meet(mid)) l = mid;
            else r = mid;
        }
        while (meet(l+1)) l++;
        printf("%d\n",l);
    }
    return 0;
}

/*
3
1 1 0
NYN
YNY
NYN
7 
7 3 3 2 0 0 5 
NYNNNNN 
YNYYNNN 
NYNYYNN 
NYYNYNN 
NNYYNNN 
NNNNNNY 
NNNNNYN
4
2 2 0 0
NNYN
NNNY
YNNN
NYNN
*/

uva 12264 Risk

原文：https://www.cnblogs.com/kickit/p/10828375.html