(14750) Jerry and Tom

https://www.acmicpc.net/problem/14750

단계별로 풀어보기

54단계(네크워크 플로우 1) 3번째

 

 

 

쥐와 쥐구멍을 정점으로 두고 쥐가 들어갈 수 있는 쥐구멍에 정점을 이어주면 되는데, 이 과정을 기하로 해결해야 해서 매우 귀찮다. 이 코드에서는 모든 벽이 수직이거나 수평이라는 점을 이용해 최적화해서 시간을 많이 줄였는데, 사실 범위를 보면 그냥 모든 쥐와 쥐구멍을 이은 선분을 모든 벽을 이루는 선분과 CCW를 이용한 선분 교차 판정을 해도 충분히 작동한다. 아무튼 잘 이었다면 모든 쥐로 이어지는 가상의 시작 정점과 모든 쥐구멍에서 이어지는 가상의 도착 정점을 만들어 네트워크 플로우로 최대 유량을 계산하면 된다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define SIZE 303
#define INF 1000000
using namespace std;
typedef pair<int,int> p;

struct Edge;
const int s= 301, e= 302;
vector<Edge> adj[SIZE];
int level[SIZE], work[SIZE];

struct Edge{
  int to, cap, flux, rev;
  
  Edge(int to1, int cap1, int rev1): to(to1), cap(cap1), flux(0), rev(rev1){}

  int spare(){
    return cap-flux;
  }
};

struct Line{
  int cord, start, end;
  
  Line(int cord1=0, int start1=0, int end1=1): cord(cord1), start(start1), end(end1) {}
  
  bool operator <(const Line &A) const {
    return cord<A.cord;
  }
};

double yfind(p p1, p p2, int x){
  return (double)(p2.second-p1.second)/(p2.first-p1.first)*(x-p1.first)+p1.second;
}

double xfind(p p1, p p2, int y){
  return (double)(p2.first-p1.first)/(p2.second-p1.second)*(y-p1.second)+p1.first;
}

void addedge(int u, int v, int capacity){
  int uidx= adj[u].size();
  int vidx= adj[v].size();
  
  adj[u].push_back(Edge(v, capacity, vidx));
  adj[v].push_back(Edge(u, 0, uidx));
}

bool leveling(){  
  queue<int> q;
  fill_n(level, SIZE, 0);

  level[s]= 1;
  q.push(s);

  while(!q.empty()){
    int now= q.front();
    q.pop();

    for(Edge &edge: adj[now]){
      int next= edge.to;
      
      if(!level[next] && edge.spare()>0){
        level[next]= level[now]+1;
        q.push(next);
      }
    }
  }

  return level[e];
}

int dfs(int now, int nowflow){
  if(now==e)  return nowflow;

  for(int &i= work[now];i<adj[now].size();i++){
    Edge &edge= adj[now][i];
    int next= edge.to;

    if(level[next]==level[now]+1 && edge.spare()>0){
      int flow= dfs(next, min(nowflow, edge.spare()));

      if(flow>0){
        adj[now][i].flux+= flow;
        adj[next][edge.rev].flux-= flow;
        
        return flow;
      }
    }
  }

  return 0;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, k, h, m, cnt= 0;

  cin >> n >> k >> h >> m;
  
  vector<p> house(n+1), hole(h), mouse(m);
  
  for(int i=0;i<n;i++)  cin >> house[i].first >> house[i].second;
  house[n]= house[0];
  for(int i=0;i<h;i++)  cin >> hole[i].first >> hole[i].second;
  for(int i=0;i<m;i++)  cin >> mouse[i].first >> mouse[i].second;
  
  vector<Line> vert, hor;
  
  for(int i=0;i<n;i++){
    if(house[i].first==house[i+1].first){
      vert.push_back(Line(house[i].first, min(house[i].second, house[i+1].second), max(house[i].second, house[i+1].second)));
    }else{
      hor.push_back(Line(house[i].second, min(house[i].first, house[i+1].first), max(house[i].first, house[i+1].first)));
    }
  }
  
  sort(vert.begin(), vert.end());
  sort(hor.begin(), hor.end());
  
  for(int i=0;i<m;i++){
    for(int j=0;j<h;j++){
      int xstart= min(mouse[i].first,hole[j].first);
      int xend= max(mouse[i].first,hole[j].first);
      int ystart= min(mouse[i].second,hole[j].second);
      int yend= max(mouse[i].second,hole[j].second);
      bool can= true;

      for(int t= (upper_bound(vert.begin(), vert.end(), Line(xstart))-vert.begin());can&&t<vert.size()&&vert[t].cord<xend;t++){
        double y= yfind(mouse[i], hole[j], vert[t].cord);
        if(vert[t].start<=y && y<=vert[t].end){
          can= false;
        }
      }
      for(int t= (upper_bound(hor.begin(), hor.end(), Line(ystart))-hor.begin());can&&t<hor.size()&&hor[t].cord<yend;t++){
        double x= xfind(mouse[i], hole[j], hor[t].cord);
        if(hor[t].start<=x && x<=hor[t].end){
          can= false;
        }
      }

      if(can)  addedge(1+i, 251+j, 1);
    }
  }
  
  for(int i=1;i<=m;i++)  addedge(s, i, 1);
  for(int i=1;i<=h;i++)  addedge(250+i, e, k);
  
  while(leveling()){
    fill_n(work, SIZE, 0);
    
    while(1){
      int flow= dfs(s, INF);
      
      if(flow)  cnt+= flow;
      
      else  break;
    }
  }

  cout << (cnt==m ? "Possible" : "Impossible");

  return 0;
}