TIOJ 1253 砲打皮皮 [Graph]

poao899    1253    Accepted    392K    166MS    G++    0.67K    2010-04-05 19:03:02                          .




二分圖匹配

交錯路徑算法，O(V^3)


耶總算會co匹配了>//<


//**************************************

#include<stdio.h>
int n, k, match[1010], cCnt, mCnt, a, b;
bool con[1010][1010], vst[1010];
bool aug(int now){
	for(int i=1; i<=n; i++)
		if(!vst[i]&& con[now][i]){
			vst[i]= 1;
			if(match[i]==-1|| aug(match[i])){
				match[i]= now;
				return 1;
			}
		}
	return 0;
}
int main(){
	while(~scanf("%d%d", &n, &k)){
		if(!n&& !k) break;
		mCnt= 0;
		for(int i=1; i<=n; ++i){
			for(int j=1; j<=n; j++)
				con[i][j]= 0;
			match[i]= -1;
		}
		for(int i=0; i<k; ++i){
			scanf("%d%d", &a, &b);
			con[a][b]= 1;
		}
		for(int i=1; i<=n; ++i){
			for(int j=1; j<=n; ++j) vst[j]= 0;
			if(aug(i)) ++mCnt;
		}
		printf("Case #%d:%d\n", ++cCnt, mCnt);
	}
}