博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最大流拆点——poj3281
阅读量:5291 次
发布时间:2019-06-14

本文共 1947 字,大约阅读时间需要 6 分钟。

/*因为牛的容量为1,把牛拆点 按照s->f->cow->cow->d->t建图  */#include
#include
#include
#include
using namespace std;#define inf 0x3f3f3f3f#define maxn 10005struct Edge{
int to,nxt,c;}e[maxn<<1];int head[maxn],tot,n,f,dd,s,t;void init(){memset(head,-1,sizeof head);tot=0;}void add(int u,int v,int c){ e[tot].to=v;e[tot].c=c;e[tot].nxt=head[u];head[u]=tot++; e[tot].to=u;e[tot].c=0;e[tot].nxt=head[v];head[v]=tot++;}int d[maxn];bool bfs(){
//在残量网络上构造分层图 memset(d,0,sizeof d); queue
q; while(q.size())q.pop(); q.push(s);d[s]=1; while(q.size()){ int x=q.front();q.pop(); for(int i=head[x];i!=-1;i=e[i].nxt){ int y=e[i].to; if(d[y] || e[i].c==0)continue; q.push(y); d[y]=d[x]+1; if(y==t)return 1; } } return 0;}int dfs(int x,int flow){ if (x==t)return flow; int rest=flow; for(int i=head[x];i!=-1 && rest>0;i=e[i].nxt){ int y=e[i].to; if(e[i].c==0 || d[y]!=d[x]+1)continue; int k=dfs(y,min(rest,e[i].c)); if(!k) d[y]=0; //y点已经被增广完毕,本次dinic时不会再访问这个点 e[i].c-=k; e[i^1].c+=k; rest-=k; } return flow-rest;} int dinic(){ int ans=0; while(bfs()) while(int flow=dfs(s,inf)) ans+=flow; return ans;}/*牛编号[1,2*n],食物编号[2*n+1,n*2+f],饮料编号[2*n+f+1,2*n+f+d]*/int main(){ init(); cin>>n>>f>>dd; s=0;t=2*n+f+dd+1; for(int i=1;i<=f;i++)add(s,2*n+i,1); for(int i=1;i<=dd;i++)add(2*n+f+i,t,1); for(int i=1;i<=n;i++){ int k1,k2,F,D; cin>>k1>>k2; add(i,i+n,1);//拆点 while(k1--){ cin>>F; add(2*n+F,i,1); } while(k2--){ cin>>D; add(i+n,2*n+f+D,1); } } cout<
<<'\n';}

 

转载于:https://www.cnblogs.com/zsben991126/p/11003128.html

你可能感兴趣的文章
tensorflow的graph和session
查看>>
6-1 并行程序模拟 uva210
查看>>
JavaScript动画打开半透明提示层
查看>>
Mybatis生成resulteMap时的注意事项
查看>>
jquery-jqzoom 插件 用例
查看>>
1007. Maximum Subsequence Sum (25)
查看>>
《算法》C++代码 快速排序
查看>>
iframe的父子层跨域 用了百度的postMessage()方法
查看>>
Js apply方法与call方法详解 附ES6新写法
查看>>
linux php全能环境一键安装,小白福利!
查看>>
图片生成缩略图
查看>>
关于Mysql select语句中拼接字符串的记录
查看>>
动态规划 例子与复杂度
查看>>
[BZOJ4567][SCOI2016]背单词(Trie+贪心)
查看>>
查看oracle数据库的连接数以及用户
查看>>
【数据结构】栈结构操作示例
查看>>
中建项目环境迁移说明
查看>>
三.野指针和free
查看>>
activemq5.14+zookeeper3.4.9实现高可用
查看>>
TCP/IP详解学习笔记(3)IP协议ARP协议和RARP协议
查看>>