[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology