首页 > 搜索 > BFS搜索 > HDU 4183-Pahom on Water-网络流-[解题报告]HOJ
2015
05-23

HDU 4183-Pahom on Water-网络流-[解题报告]HOJ

Pahom on Water

问题描述 :

Pahom on Water is an interactive computer game inspired by a short story of Leo Tolstoy about a poor man who, in his lust for land, forfeits everything. The game’s starting screen displays a number of circular pads painted with colours from the visible light spectrum. More than one pad may be painted with the same colour (defined by a certain frequency) except for the two colours red and violet. The display contains only one red pad (the lowest frequency of 400 THz) and one violet pad (the highest frequency of 789 THz). A pad may intersect, or even contain another pad with a different colour but never merely touch its boundary. The display also shows a figure representing Pahom standing on the red pad.
The game’s objective is to walk the figure of Pahom from the red pad to the violet pad and return back to the red pad. The walk must observe the following rules:
1.If pad α and pad β have a common intersection and the frequency of the colour of pad α is strictly smaller than the frequency of the colour of pad β, then Pahom figure can walk from α to β during the walk from the red pad to the violet pad
2. If pad α and pad β have a common intersection and the frequency of the colour of pad α is strictly greater than the frequency of the colour of pad β, then Pahom figure can walk from α to β during the walk from the violet pad to the red pad
3. A coloured pad, with the exception of the red pad, disappears from display when the Pahom figure walks away from it.
The developer of the game has programmed all the whizzbang features of the game. All that is left is to ensure that Pahom has a chance to succeed in each instance of the game (that is, there is at least one valid walk from the red pad to the violet pad and then back again to the red pad.) Your task is to write a program to check whether at least one valid path exists in each instance of the game.

输入:

The input starts with an integer K (1 <= K <= 50) indicating the number of scenarios on a line by itself. The description for each scenario starts with an integer N (2 <= N <= 300) indicating the number of pads, on a line by itself, followed by N lines that describe the colors, locations and sizes of the N pads. Each line contains the frequency, followed by the x- and y-coordinates of the pad’s center and then the radius. The frequency is given as a real value with no more than three decimal places. The coordinates and radius are given, in meters, as integers. All values are separated by a single space. All integer values are in the range of -10,000 to 10,000 inclusive. In each scenario, all frequencies are in the range of 400.0 to 789.0 inclusive. Exactly one pad will have a frequency of “400.0” and exactly one pad will have a frequency of “789.0”.

输出:

The input starts with an integer K (1 <= K <= 50) indicating the number of scenarios on a line by itself. The description for each scenario starts with an integer N (2 <= N <= 300) indicating the number of pads, on a line by itself, followed by N lines that describe the colors, locations and sizes of the N pads. Each line contains the frequency, followed by the x- and y-coordinates of the pad’s center and then the radius. The frequency is given as a real value with no more than three decimal places. The coordinates and radius are given, in meters, as integers. All values are separated by a single space. All integer values are in the range of -10,000 to 10,000 inclusive. In each scenario, all frequencies are in the range of 400.0 to 789.0 inclusive. Exactly one pad will have a frequency of “400.0” and exactly one pad will have a frequency of “789.0”.

样例输入:

2
2 
400.0 0 0 4
789.0 7 0 2
4
400.0 0 0 4
789.0 7 0 2
500.35 5 0 2
500.32 5 0 3

样例输出:

Game is NOT VALID
Game is VALID

题意:

T个测试数据

n个圆

下面 fre x y r 表示圆的频率 坐标和半径

要求:

从频率为400(最小的) 圆 走到频率为789(最大)的圆,再走回来,除起点每个点只能经过一次

问这样的路径是否存在

 

走法:从400->789时经过的圆频率只增不减, 只能走相交的圆

          反之则频率只减不增,也只能走相交的圆

 

建图:

以789为源点, 400为汇点

其他点拆点拆成2个点,自己连自己,cap=1表示这个点只能走一次

 

然后跑一边最大流,当汇点流>=2时说明有这样的路径

 

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define N 605
#define inf 10000
#define ll int

using namespace std;
inline ll Max(ll a,ll b){return a>b?a:b;}
inline ll Min(ll a,ll b){return a<b?a:b;}
struct node{
	double fre;
	int x,y, r;
}p[N], s, t;
bool Cross(node a,node b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) < (a.r+b.r)*(a.r+b.r);
}

struct Edge{
	int from, to, cap, nex;
}edge[N*20];
int head[N], edgenum;
void addedge(int u, int v, int cap){
	Edge E ={u, v, cap, head[u]};
	edge[edgenum] = E;
	head[u] = edgenum++;
}

int sign[N*4];
bool BFS(int from, int to){
	memset(sign, -1, sizeof(sign));
	sign[from] = 0;

	queue<int>q;
	q.push(from);
	while( !q.empty() ){
		int u = q.front(); q.pop();
		for(int i = head[u]; i!=-1; i = edge[i].nex)
		{
			int v = edge[i].to;
			if(sign[v]==-1 && edge[i].cap)
			{
				sign[v] = sign[u] + 1, q.push(v);
				if(sign[to] != -1)return true;
			}
		}
	}
	return false;
}
int Stack[N*4], top, cur[N*4];
int dinic(int from, int to){

	int ans = 0;
	while( BFS(from, to) )
	{
		memcpy(cur, head, sizeof(head));
		int u = from;		top = 0;
		while(1)
		{
			if(u == to)
			{
				int flow = inf, loc;//loc 表示 Stack 中 cap 最小的边
				for(int i = 0; i < top; i++)
					if(flow > edge[ Stack[i] ].cap)
					{
						flow = edge[Stack[i]].cap;
						loc = i;
					}

					for(int i = 0; i < top; i++)
					{
						edge[ Stack[i] ].cap -= flow;
						edge[Stack[i]^1].cap += flow;
					}
					ans += flow;
					top = loc;
					u = edge[Stack[top]].from;
			}
			for(int i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标
				if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
			if(cur[u] != -1)
			{
				Stack[top++] = cur[u];
				u = edge[ cur[u] ].to;
			}
			else
			{
				if( top == 0 )break;
				sign[u] = -1;
				u = edge[ Stack[--top] ].from;
			}
		}
	}
	return ans;
}
ll n;

int main(){
	int T, i, j; scanf("%d",&T);
	while(T--)
	{
		memset(head, -1, sizeof(head)); edgenum = 0;

		scanf("%d",&n);
		for(i = 1; i <= n; i++)
			{
				scanf("%lf %d %d %d",&p[i].fre,&p[i].x,&p[i].y,&p[i].r);
				if(p[i].fre == 400)
					t = p[i],i--,n--;
				else if(p[i].fre == 789)
					s = p[i],i--,n--;
		}
		if(Cross(s,t)){printf("Game is VALID\n");continue;}
		for(i = 1; i <= n; i++)
		{
			addedge(i,i+n,1);
			addedge(i+n,i,0);
			if(Cross(p[i],s))
			{
				addedge(0,i,1);
				addedge(i,0,0);
			}
			if(Cross(p[i],t))
			{
				addedge(i+n, 2*n+10,1);
				addedge(2*n+10,i+n,0);
			}
			for(j = 1; j <= n; j++)
				if(Cross(p[i],p[j]) && i!=j)
				{
					if(p[i].fre>p[j].fre)
					{
						addedge(i+n,j,1);
						addedge(j,i+n,0);
					}
					else
					{
						addedge(j+n,i,1);
						addedge(i,j+n,0);
					}
				}
		}
		int ans = dinic(0, 2*n+10);
		if(ans < 2)printf("Game is NOT VALID\n");
		else printf("Game is VALID\n");

	}
	return 0;
}

 

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acmmmm/article/details/13760967