PKU 3041 Asteroids

問題文→ 3041 -- Asteroids

N*Nの格子上にK個の小惑星があります。小惑星iの位置は(R[i],C[i])にあります。縦または横一直線上の小惑星をすべて一発のビームで破壊できる強力な武器があり、これを用いてすべての小惑星を破壊するために必要な最小の発射回数を求めなさい。

普通に探索するとO(2^(2*n))とかかかる。
ビームの撃ち方は縦、横2通りしかないのでビームの撃ち方を頂点、それによって破壊できる惑星を辺とした二部マッチングに帰着できる(quote from 蟻本)

こんな賢いやり方思いつかないよ...

ということで初のフロー問題。

今回は二部マッチングの最小点カバー問題なので、Fold-Fulkersonで普通に最大マッチングを求めた。
ちなみに最大マッチングは「互いに端点を共有しない辺集合M⊆E」の事。
二部マッチングの場合はこれが最小点カバーにもなる。

コメント添えながらコード書くと頭に入りやすいですね！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<cstdlib>
#include<climits>
#include<cstring>
#include<queue>
#include<deque>
#include<set>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EPS 0.0001
using namespace std;
typedef long long ll;
const int MAX_V=1000000;
struct edge{int to,cap,rev;}; //行き先、容量、逆辺のインデックス
vector<edge>G[MAX_V];//隣接リスト
bool used[MAX_V];//閉路確認

//fromからtoへ容量capの辺を追加(逆変も容量0で追加)
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; //流せない
}

const int INF=1<<30;
int max_flow(int s,int t){
  int flow=0;
  //閉路なしで流せるだけ流すという作業を繰り返す
  //流せたら逆辺を追加するので、残余パスが増えている可能性がある
  for(;;){
    memset(used,0,sizeof(used));
    int f=dfs(s,t,INF);
    if(f==0) return flow;
    flow+=f;
  }
  return 0;
}


int R[MAX_V],C[MAX_V];
int N,K;

//二部マッチング
int Matching(){
  int s=N+N+1,t=s+1;
  for(int i=0;i<N;i++) add_edge(s,i,1);
  for(int i=0;i<N;i++) add_edge(N+i,t,1);
  
  for(int i=0;i<K;i++)
    add_edge(R[i]-1,N+C[i]-1,1);
  
  return max_flow(s,t);
}
int main(){
  cin>>N>>K;
  REP(i,K) cin>>R[i]>>C[i];
  cout<<Matching()<<endl;
}