[TIOJ] 1253. 砲打皮皮

題目連結:http://tioj.infor.org/problems/1253

---

本題可以轉化為二分圖最小點覆蓋，因為不妨考慮把每隻皮皮當作邊，連接著一個列跟欄(如下圖)
而我們要求的不就是找到最少的列或欄使得每隻皮皮都被炸掉，剛好就是找到最少的點覆蓋所有的邊，而且這樣轉還有一個好處就是他保證會是二分圖，所以我們要做的事就是找到最小點覆蓋。不過二分圖最小點覆蓋又該如何找呢？可以證明，其實二分圖最小點覆蓋的數量就等於二分圖最大匹配的數量，因此問題又被轉化成了二分圖最大匹配，二分圖最大匹配有很多種作法，一種是新增一個起點連接所有左半圖，並新增一個終點連接所有右半圖，把問題又轉成最大流的流量，所以可以用dinic或ford fulkerson之類的演算法寫掉。不過因為是二分圖，所以其實有好的找匹配數的方法，就對於某一個點如果其還未被匹配，則看他可不可以跟其他點匹配，如果與他相鄰的某個點已經被匹配過了，那就請他試試看可不可以換點，如此遞迴下去即可求得最大匹配數。
p.s 詳細證明可以看演算法筆記

#include <bits/stdc++.h>
using namespace std;

#define N 1000

int cnt=1;
int ans=0;
bitset<N+5> visited;
vector<int> X[N+5], Y[N+5];
int matchX[N+5], matchY[N+5];
inline void init(int);
bool DFS(int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,k;
	cin>>n>>k;
	while(n!=0||k!=0){
		init(n);
		for(int i=0;i<k;i++){
			int s,e;
			cin>>s>>e;
			X[s].push_back(e);
			Y[e].push_back(s);
		}
		for(int i=1;i<=n;i++){
			visited.reset();
			if(DFS(i))ans++;
		}
		cout<<"Case #"<<cnt++<<':'<<ans<<'\n';
		cin>>n>>k;
	}
	return 0;
}

inline void init(int n){
	ans=0;
	visited.reset();
	for(int i=1;i<=n;i++){
		X[i].clear();
		Y[i].clear();
		matchX[i]=-1;
		matchY[i]=-1;
	}
}

bool DFS(int x){
	for(auto i:X[x]){
		if(visited[i]) continue;
		visited[i]=1;
		if(matchY[i]==-1||DFS(matchY[i])){
			matchY[i]=x;
			matchX[x]=i;
			return 1;
		}
	}
	return 0;
}