CQOI2014 危桥

wjh15101051's space

卧薪尝胆，厚积薄发。

CQOI2014 危桥

Date: Thu Mar 14 19:25:51 CST 2019

In Category: NoCategory

Description：

无向图有一些道路只能通行 $2$ 次，问能否在 $a_1$ 和 $a_2$ 之间往返 $a_n$ 次并在 $b_1$ 和 $b_2$ 之间往返 $b_n$ 次。

$1\leqslant n\leqslant 50$

Solution：

首先一个显然的想法是建网络流图然后源点连 $a_1,b_1$ 汇点连 $a_2,b_2$ 判断是否满流。

但是这样有一个问题就是可能找到了 $a_1\to b_2,a_2\to b_1$ 的路径，然后一个神仙做法是源点连 $a_1,b_2$ 汇点连 $a_2,b_1$ 再跑一次就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,a1,a2,an,b1,b2,bn;

#define MAXN 60

char getc()

{

	register char c = getchar();

	while(c != 'O' && c != 'N' && c != 'X')c = getchar();

	return c;

}

char c[MAXN][MAXN];

struct edge

{

	int to,nxt,f;

}e[MAXN * MAXN * 4];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int f)

{

	e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

	return;

}

int s,t;

int ch[MAXN];

bool BFS()

{

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

#define INF 0x3f3f3f3f

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

	while(~scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn))

	{

		an *= 2;bn *= 2;

		s = n + 1;t = s + 1;

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

			for(int j = 0;j < n;++j)

				c[i][j] = getc();

		edgenum = 0;

		memset(lin,-1,sizeof(lin));

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

		{

			for(int j = 0;j < n;++j)

			{

				if(c[i][j] == 'N')add(i,j,INF);

				if(c[i][j] == 'O')add(i,j,2);

			}

		}

		add(s,a1,an);add(a2,t,an);

		add(s,b1,bn);add(b2,t,bn);

		if(dinic() < an + bn)

		{

			puts("No");

			continue;

		}

		edgenum = 0;

		memset(lin,-1,sizeof(lin));

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

		{

			for(int j = 0;j < n;++j)

			{

				if(c[i][j] == 'N')add(i,j,INF);

				if(c[i][j] == 'O')add(i,j,2);

			}

		}

		add(s,a1,an);add(a2,t,an);

		add(s,b2,bn);add(b1,t,bn);

		if(dinic() < an + bn)

		{

			puts("No");

			continue;

		}

		puts("Yes");

	}

	return 0;

}

In tag: 图论-dinic

wjh15101051