首页 > 代码库 > poj 1149 PIGS 最大流
poj 1149 PIGS 最大流
题意:
有 M 个猪圈每个猪圈里初始时有若干头猪,开始时所有猪圈都是关闭的。 依次来了 N 个顾客,每个顾客分别打开指定的几个猪圈,从中买若干头猪,每个顾客最多能买的猪数是确定的。 每个顾客走后,他打开的那些猪圈中的猪可以自由流动,然后所有猪圈重新关上。
分析:
最大流,关键是处理顾客i买完猪后他打开的猪圈可以自由流动:假设j在i之后来,他们都能打开猪圈k,那么i是可以帮j买猪的,i买完他要的猪后可以把x头赶到k里,之后j过来从k里拿走这x头猪,这就相当于有x头猪是i帮j买的。所以如果j在i之后来,他们都能打开猪圈k,那么要加边j->i。
代码:
//poj 1149 //sep9 #include <iostream> #include <queue> using namespace std; const int maxN=20000; const int maxM=1000000; struct Edge { int v,f,nxt; }e[maxM*2+10]; queue<int> que; int src,sink; int g[maxN+10]; int nume; bool vis[maxN+10]; int dist[maxN+10]; int key[120][1200]; void addedge(int u,int v,int c) { e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume; } void init() { memset(g,0,sizeof(g)); nume=1; } void bfs() { while(!que.empty()) que.pop(); vis[src]=true; que.push(src); while(!que.empty()){ int u=que.front();que.pop(); for(int i=g[u];i;i=e[i].nxt) if(e[i].f&&!vis[e[i].v]){ que.push(e[i].v); dist[e[i].v]=dist[u]+1; vis[e[i].v]=true; } } } int dfs(int u,int delta) { if(u==sink) return delta; int ret=0; for(int i=g[u];delta&&i;i=e[i].nxt) if(e[i].f&&dist[e[i].v]==dist[u]+1){ int dd=dfs(e[i].v,min(e[i].f,delta)); e[i].f-=dd; e[i^1].f+=dd; delta-=dd; ret+=dd; } return ret; } int dinic() { int ret=0; while(1){ memset(vis,0,sizeof(vis)); memset(dist,0,sizeof(dist)); bfs(); if(!vis[sink]) break; ret+=dfs(src,INT_MAX); } return ret; } int main() { int i,m,n; scanf("%d%d",&m,&n); init(); src=http://www.mamicode.com/0,sink=m+n+1;>poj 1149 PIGS 最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。