5689:Pahom on Water

問題文
https://icpcarchive.ecs.baylor.edu/external/56/5689.pdf

色のついた円が与えられる。各データセットには色が400.0の円と789.0の円がひとつずつ含まれる。この円の上を通って、400.0の円から789.0の円に行って戻ってくることができるかどうか判定せよ。ただし一度通った円の上は通ることができず、円が交わっている場合のみ移動できる。また、400.0の円から789.0の円に行くときは色が小さい円から大きい円にしか移動できず、789.0の円から400.0の円に向かうときには色が大きい円から小さい円にしか移動できない。

蟻本のフローのところに載ってるPOJ No.2135と考え方は同じ。色が小さい円から大きい円に流量1の辺を張る。このグラフの上で、400.0の円から789.0の円への辺を共有しないようなパスが２つ以上あればよい。最小カットが2以上であればそのような２つのパスが存在する。

#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cfloat>
#include<queue>
#define MAX_V 301
#define INF (1<<29)

using namespace std;
 
double EPS = 1e-10;

struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}

  bool operator == ( const point &p ) const {
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }
};
 
struct circle{
  point p;
  double r,f;
  circle(){}
  circle(point p, double r) : p(p) , r(r){}
};
 
int circles_intersection(circle A,circle B){
  double d=sqrt(pow(A.p.x-B.p.x,2)+pow(A.p.y-B.p.y,2));
  if(d>A.r+B.r)return 0;
  return 1;
}
       
struct edge{int to,cap,rev;};

int V;
vector<edge>G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  for(int i=0;i<G[v].size();i++){
    edge& e=G[v][i];
    if(!used[e.to] && e.cap>0){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
	e.cap-=d;
	G[e.to][e.rev].cap+=d;
	return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow=0;
  for(;;){
    fill(used,used+MAX_V,0);
    int f=dfs(s,t,INF);
    if(f==0)return flow;
    flow+=f;
  }
}

int main(void){
 
  int tc;
  cin >> tc;
  while(tc--){
    for(int i=0;i<MAX_V;i++)G[i].clear();
    cin >> V;
    vector<circle>c(V); 
    int s,t;
    for(int i=0;i<V;i++){
      cin >> c[i].f >> c[i].p.x >> c[i].p.y >> c[i].r;
      if(c[i].f==400.0)s=i;
      if(c[i].f==789.0)t=i;
    }
    
    for(int i=0;i<c.size();i++){
      for(int j=0;j<c.size();j++){
	int res=circles_intersection(c[i],c[j]);
	if(c[i].f<c[j].f &&  res!=0)add_edge(i,j,1);
      }
    }
    
    if(max_flow(s,t)>=2)cout << "Game is VALID" << endl;
    else cout << "Game is NOT VALID" << endl;
  }
  return 0;
}