uva 12264 Risk

题意：

有很多个阵地，分为敌方和己方，每个士兵可以移动到相邻的己方的阵地，但是只能移动一步。

现在要让与敌方相邻的阵地中士兵最少的最多。

思路：

最少的最多，那显然二分。

二分这个最少的值。拆点，敌方阵地不管，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

题意：

思路：

STD：

最新文章

热门文章