首页 > 代码库 > poj3281网络流之最大流
poj3281网络流之最大流
加一个源点和汇点,把每头牛拆成两个点,不拆点的话可能会出现多对食物与饮料被一个牛享用的情况,拆点后流量为1,不能同时通过了
然后用最大流处理,每个链接边都是1
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=400+5,maxn=16,inf=999999; int c[N][N],pre[N]; bool vis[N]; int s,t,n,food,drink; bool bfs() { memset(pre,0,sizeof pre); memset(vis,0,sizeof vis); vis[s]=1; queue<int>q; q.push(s); while(!q.empty()){ int k=q.front(); if(k==t)return 1; q.pop(); for(int i=0;i<=n+n+food+drink+1;i++) { if(!vis[i]&&c[k][i]) { vis[i]=1; q.push(i); pre[i]=k; } } } return 0; } int max_flow() { int ans=0; while(1){ if(!bfs())return ans; int minn=9999999; for(int i=t;i!=s;i=pre[i]) minn=min(minn,c[pre[i]][i]); for(int i=t;i!=s;i=pre[i]) { c[pre[i]][i]-=minn; c[i][pre[i]]+=minn; } ans+=minn; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>food>>drink; memset(c,0,sizeof c); for(int i=1;i<=n;i++) { int a,b,k; cin>>a>>b; while(a--){ cin>>k; c[k][i+food]=1; } while(b--){ cin>>k; c[i+n+food][k+n+n+food]=1; } } s=0,t=n+n+food+drink+1; for(int i=1;i<=n;i++)c[food+i][food+n+i]=1; for(int i=1;i<=food;i++)//源点为0,汇点为n+food+drink+1 c[0][i]=1; for(int i=1;i<=drink;i++) c[n+n+food+i][n+n+food+drink+1]=1; cout<<max_flow()<<endl; return 0; }
poj3281网络流之最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。