首页 > 代码库 > [USACO4.2]完美的牛栏The Perfect Stall

[USACO4.2]完美的牛栏The Perfect Stall

题目:USACO Training 4.2(在官网上提交需加文件输入输出)、洛谷P1894。

题目大意:有n头奶牛m个牛栏,每头牛只会在自己喜欢的牛栏里产奶,问一次最多有多少奶牛能产奶。

解题思路:二分图匹配。这里我用了网络流,先建立超级源点和超级汇点,跑最大流即可。以下是Dinic算法的代码。

C++ Code:

 

#include<cstdio>#include<queue>#include<cstring>#include<algorithm>#include<vector>using namespace std;int n,m,level[405],iter[405];queue<int>q;struct edges{	int to,cap,rev;	edges(int t,int c,int r):to(t),cap(c),rev(r){}};vector<edges>G[405];inline void addedge(int from,int to){	G[from].push_back(edges(to,1,G[to].size()));	G[to].push_back(edges(from,0,G[from].size()-1));}void bfs(int s){	memset(level,-1,sizeof level);	level[s]=0;	q.push(s);	while(!q.empty()){		int u=q.front();q.pop();		for(int i=0;i<G[u].size();++i){			edges& e=G[u][i];			if(e.cap>0&&level[e.to]<0){				level[e.to]=level[u]+1;				q.push(e.to);			}		}	}}int dfs(int u,int t,int f){	if(u==t)return f;	for(int& i=iter[u];i<G[u].size();++i){		edges& e=G[u][i];		if(e.cap>0&&level[e.to]>level[u]){			int d=dfs(e.to,t,min(f,e.cap));			if(d){				e.cap-=d;				G[e.to][e.rev].cap+=d;				return d;			}		}	}	return 0;}int max_flow(int s,int t){	int flow=0;	for(;;){		bfs(s);		if(level[t]<0)return flow;		memset(iter,0,sizeof iter);		int f;		while(f=dfs(s,t,1))flow+=f;	}}int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i){		addedge(0,i);		int k;		scanf("%d",&k);		for(;k--;){			int x;			scanf("%d",&x);			addedge(i,x+n);		}	}	for(int i=1;i<=m;++i)addedge(i+n,n+m+1);	printf("%d\n",max_flow(0,n+m+1));	return 0;}

 

[USACO4.2]完美的牛栏The Perfect Stall