首页 > 代码库 > HDU4183_Pahom on Water

HDU4183_Pahom on Water

2024-07-10 18:07:39   220人阅读

题意为给你若干个圆，每个圆的颜色对应一个频率，如果两个圆有公共部分，那么这两个圆之间可以走，你可以从起点开始，从频率小的圆走向频率大的圆并且到达终点后，从频率大的圆走向频率小的圆，最终回到起点，路径中每个圆只能走一次，是否存在一个满足条件的方案。

这样的，把红点当做起点，把紫点当做终点，如果两个圆相交，那么从频率小的圆连接一条边指向频率大的圆，边容量为1。如此一来，相当于求起点到终点的最大流量是否不小于2即可。因为只要不小于2，说明有两条不相交的路径达到终点，只要把其中的一条路径反向即可。

由于这里的最大流量可能很多，为了避免不必要的耗时，我们可以再找到两条路径后直接退出。更好实现的方法是跑两次EK，看看是否都能找到增广路就可以啦。

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <queue>#include <vector>#define maxn 333using namespace std;vector<int> v[maxn];int c[maxn][maxn],pre[maxn],tag[maxn];bool can[maxn];int n,m,s,t,T,ans,N=1;double hz[maxn];int x[maxn],y[maxn],r[maxn];int Q[maxn],bot,top;int dis(int x1,int y1,int x2,int y2){	return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);}void _init(){	ans=0;	for (int i=1; i<=n; i++)	{		v[i].clear();		for (int j=1; j<=n; j++) c[i][j]=0;	}	for (int i=1; i<=n; i++)	{		scanf("%lf%d%d%d",&hz[i],&x[i],&y[i],&r[i]);		if (hz[i]==400) s=i;		if (hz[i]==789) t=i;	}}void graph_build(){	for (int i=1; i<=n; i++)		for (int j=1; j<=n; j++)		{			if (hz[j]<=hz[i]) continue;			if (dis(x[i],y[i],x[j],y[j])<(r[i]+r[j])*(r[i]+r[j]))				c[i][j]=1,v[i].push_back(j),v[j].push_back(i);		}}bool EK(int TAG){	Q[bot=top=1]=s,tag[s]=TAG;	while (bot<=top)	{		int cur=Q[bot++];		for (unsigned i=0; i<v[cur].size(); i++)			if (tag[v[cur][i]]!=TAG && c[cur][v[cur][i]]>0)			{				tag[v[cur][i]]=TAG;				Q[++top]=v[cur][i];				pre[v[cur][i]]=cur;				if (v[cur][i]==t)				{					for (int k=t; k!=s; k=pre[k]) c[pre[k]][k]=0,c[k][pre[k]]=1;					return true;				}			}	}	return false;}int main(){	scanf("%d",&T);	while (T--)	{		scanf("%d",&n);		_init(); 		graph_build();		if (c[s][t])		{			puts("Game is VALID");			continue;		}		ans=1;		for (int i=1; i<=2; i++) 			if (!EK(++N)) 			{				ans=0;				break;			}		if (ans) puts("Game is VALID");			else puts("Game is NOT VALID");	}	return 0;}

　　


联系
我们