首页 > 代码库 > POJ 3281 Dining（网络流拆点）
POJ 3281 Dining（网络流拆点）
【题目链接】 http://poj.org/problem?id=3281
【题目大意】
给出一些食物，一些饮料，每头牛只喜欢一些种类的食物和饮料，
但是每头牛最多只能得到一种饮料和食物，问可以最多满足几头牛的要求
即同时得到喜欢的饮料和食物
【题解】
建立一个源点连接食物，汇点连接饮料，中间连接牛，
为了防止同一头牛占用多个资源，所以我们对牛进行拆点，限流为1.
【代码（Isap）】
#include <cstdio>#include <cstring>using namespace std; const int N=30010,inf=~0U>>2;struct edge{int t,f;edge*nxt,*pair;}*g[N],*d[N],pool[N],*cur=pool;int sum,ff,dd,x,fi,di,cnt,cas,i,u,v,cost,n,m,S,T,h[N],gap[N],maxflow;int min(int x,int y){return x<y?x:y;}void add(int s,int t,int w){ edge*p=cur++;p->t=t;p->f=w;p->nxt=g[s];g[s]=p; p=cur++;p->t=s;p->f=0;p->nxt=g[t];g[t]=p; g[s]->pair=g[t];g[t]->pair=g[s];}int sap(int v,int flow){ if(v==T)return flow; int rec=0; for(edge*p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&p->f){ int ret=sap(p->t,min(flow-rec,p->f)); p->f-=ret;p->pair->f+=ret;d[v]=p; if((rec+=ret)==flow)return flow; }if(!(--gap[h[v]]))h[S]=T; gap[++h[v]]++;d[v]=g[v]; return rec;}int main(){ while(~scanf("%d%d%d",&n,&fi,&di)){ maxflow=0; sum=n+fi+di+n+2; S=sum-1; T=sum; for(cur=pool,i=sum;i<=sum;i++)g[i]=d[i]=NULL,h[i]=gap[i]=0; for(i=1;i<=n;i++){ scanf("%d%d",&ff,&dd); for(int j=0;j<ff;j++){scanf("%d",&x);add(x+n,i,1);} for(int j=0;j<dd;j++){scanf("%d",&x);add(i+n+fi+di,x+n+fi,1);} add(i,i+n+fi+di,1); }for(int i=1;i<=fi;i++)add(S,i+n,1); for(int i=1;i<=di;i++)add(i+n+fi,T,1); for(gap[0]=T,i=1;i<=T;i++)d[i]=g[i]; while(h[S]<T)maxflow+=sap(S,inf); printf("%d\n",maxflow); }return 0;}【代码（Dinic）】
#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;const int INF=0x3f3f3f3f;const int MAX_V=500;struct edge{int to,cap,rev;}; vector<edge> G[MAX_V];int level[MAX_V],iter[MAX_V];void add_edge(int from,int to,int cap){ G[from].push_back((edge){to,cap,G[to].size()}); G[to].push_back((edge){from,0,G[from].size()-1});}void bfs(int s){ memset(level,-1,sizeof(level)); queue<int> que; level[s]=0; que.push(s); while(!que.empty()){ int v=que.front(); que.pop(); for(int i=0;i<G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&level[e.to]<0){ level[e.to]=level[v]+1; que.push(e.to); } } }}int dfs(int v,int t,int f){ if(v==t)return f; for(int &i=iter[v];i<G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&level[v]<level[e.to]){ int d=dfs(e.to,t,min(f,e.cap)); if(d>0){ 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,INF))>0){ flow+=f; } }}const int MAX_N=100;const int MAX_F=100;const int MAX_D=100;int N,F,D;bool likeF[MAX_N][MAX_F];bool likeD[MAX_N][MAX_D];void init(){ int fi,di; memset(likeF,0,sizeof(likeF)); memset(likeD,0,sizeof(likeD)); for(int i=0;i<N;i++){ scanf("%d%d",&fi,&di); for(int j=0;j<fi;j++){ int x;scanf("%d",&x); likeF[i][x-1]=1; } for(int j=0;j<di;j++){ int x;scanf("%d",&x); likeD[i][x-1]=1; } }}void solve(){ int s=N*2+F+D,t=s+1; for(int i=0;i<=t;i++)G[i].clear(); for(int i=0;i<F;i++)add_edge(s,N*2+i,1); for(int i=0;i<D;i++)add_edge(N*2+F+i,t,1); for(int i=0;i<N;i++){ add_edge(i,N+i,1); for(int j=0;j<F;j++){ if(likeF[i][j])add_edge(N*2+j,i,1); } for(int j=0;j<D;j++){ if(likeD[i][j])add_edge(N+i,N*2+F+j,1); } }printf("%d\n",max_flow(s,t));}int main(){ while(~scanf("%d%d%d",&N,&F,&D)){ init(); solve(); }return 0;}POJ 3281 Dining（网络流拆点）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。