首页 > 代码库 > [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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。