Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 772 Accepted Submission(s):
355
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<algorithm>
#define INF 0x7ffffff
#define MAX 10010
#define MAXM 100100
#define eps 1e-5
#define DD double
using namespace std;
DD pad[MAX],x[MAX],y[MAX],r[MAX];
struct node
{
int from,to,cap,flow,next;
}edge[MAXM];
int vis[MAX],dis[MAX];
int cur[MAX];
int head[MAX],ans;
void init()
{
ans=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v,int w)
{
edge[ans]={u,v,w,0,head[u]};
head[u]=ans++;
edge[ans]={v,u,0,0,head[v]};
head[v]=ans++;
}
int judge(int i,int j)//判断两个光谱是否相交
{
if((sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j])<0)
return 1;
return 0;
}
int bfs(int beg,int end)
{
memset(vis,0,sizeof(vis));
memset(dis,-1,sizeof(dis));
queue<int>q;
while(!q.empty())
q.pop();
q.push(beg);
vis[beg]=1;
dis[beg]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
node E=edge[i];
if(!vis[E.to]&&E.cap>E.flow)
{
dis[E.to]=dis[u]+1;
vis[E.to]=1;
if(E.to==end) return 1;
q.push(E.to);
}
}
}
return 0;
}
int dfs(int x,int a,int end)
{
if(a==0||x==end)
return a;
int flow=0,f;
for(int &i=cur[x];i!=-1;i=edge[i].next)
{
node& E=edge[i];
if(dis[E.to]==dis[x]+1&&(f=dfs(E.to,min(a,E.cap-E.flow),end))>0)
{
E.flow+=f;
edge[i^1].flow-=f;
flow+=f;
a-=f;
if(a==0) break;
}
}
return flow;
}
int Maxflow(int beg,int end)
{
int flow=0;
while(bfs(beg,end))
{
memcpy(cur,head,sizeof(head));
flow+=dfs(beg,INF,end);
}
return flow;
}
int main()
{
int t,n,m,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
for(i=1;i<=n;i++)
scanf("%lf%lf%lf%lf",&pad[i],&x[i],&y[i],&r[i]);
for(i=1;i<=n;i++)
{
if(fabs(pad[i]-789.0)<=eps)//紫色光圈连接源点
add(0,i,2);
if(fabs(pad[i]-400.0)<=eps)//红则光谱连接汇点
add(i,n+1,2);
for(j=1;j<=n;j++)
{
if(i!=j)//判断到同一个光圈时跳过
{
if(judge(i,j)&&pad[i]>pad[j])//光圈相交且第一个的光普大
{
add(i,j,1);
}
}
}
}
if(Maxflow(0,n+1)==2)
printf("Game is VALID\n");
else
printf("Game is NOT VALID\n");
}
return 0;
}
原文:http://www.cnblogs.com/tonghao/p/4953903.html