HDU [P3605] Escape

二分图多重匹配

改进版的匈牙利,加入了一个cnt数组作为找到增广路的标志

本题有一个重要的优化见注释

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

using namespace std;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return fh*rv;

}

const int MAXN=100005;

int n,m,cnt[12],match[12][MAXN],g[MAXN][12],lim[12];

bool f[12];

bool hungarian(int u){

	for(int i=1;i<=g[u][0];i++){

		int v=g[u][i];

		if(!f[v]){

			f[v]=1;

			if(cnt[v]<lim[v]){

				match[v][++cnt[v]]=u;

				return 1;

			}

			for(int j=1;j<=cnt[v];j++){

				if(hungarian(match[v][j])){

					match[v][j]=u;

					return 1;

				}

			}

		}

	}

	return 0;

}

int main(){

	while(~scanf("%d%d",&n,&m)){

		memset(g,0,sizeof(g));

		//memset(match,0,sizeof(match));

		memset(cnt,0,sizeof(cnt));

		memset(lim,0,sizeof(lim));

		for(int i=1;i<=n;i++){

			for(int j=1;j<=m;j++){

				int t=init();

				if(t) g[i][++g[i][0]]=j;

			}

		}

		for(int i=1;i<=m;i++) lim[i]=init();

		int ans=0;

		for(int i=1;i<=n;i++){

			memset(f,0,sizeof(f));

			if(!hungarian(i)) {ans=1;break;}//一旦搜不到增广路就退出

		}

		if(!ans) cout<<"YES"<<endl;

		else cout<<"NO"<<endl;

	}

}