首页 > 代码库 > hdu4292 Food 最大流模板题
hdu4292 Food 最大流模板题
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4292
题意：水和饮料，建图跑最大流模板。
我用的是学长的模板，最然我还没有仔细理解，不过这都不重要直接贴就行了。
下面是AC代码，以后就当做最大流的模板来用了。
代码：
#include<cstdio> #include<iostream> using namespace std; const int oo=1e9; const int mm=2e5+5; const int mn=1e5+5; int node,src,dest,edge; int ver[mm],flow[mm],Next[mm]; int head[mn],work[mn],dis[mn],q[mn]; int Min(int a,int b) { return a<b?a:b; } void prepare(int _node,int _src,int _dest) { node=_node,src=http://www.mamicode.com/_src,dest=_dest; for(int i=0; i<node; ++i)head[i]=-1; edge=0; } void Addedge(int u,int v,int c) { ver[edge]=v,flow[edge]=c,Next[edge]=head[u],head[u]=edge++; ver[edge]=u,flow[edge]=0,Next[edge]=head[v],head[v]=edge++; } bool Dinic_bfs() { int i,u,v,l,r=0; for(i=0; i<node; ++i)dis[i]=-1; dis[q[r++]=src]=0; for(l=0; l<r; ++l) for(i=head[u=q[l]]; i>=0; i=Next[i]) if(flow[i]&&dis[v=ver[i]]<0) { dis[q[r++]=v]=dis[u]+1; if(v==dest)return 1; } return 0; } int Dinic_dfs(int u,int exp) { if(u==dest)return exp; for(int &i=work[u],v,tmp; i>=0; i=Next[i]) if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,Min(exp,flow[i])))>0) { flow[i]-=tmp; flow[i^1]+=tmp; return tmp; } return 0; } int Dinic_flow() { int i,ret=0,delta; while(Dinic_bfs()) { for(i=0; i<node; ++i) work[i]=head[i]; while(delta=Dinic_dfs(src,oo)) ret+=delta; } return ret; } int main() { char s[205]; int n,f,d,t; while(scanf("%d%d%d",&n,&f,&d)==3) { prepare(n*2+f+d+2,0,n*2+f+d+1); for(int i=1; i<=f; i++) { scanf("%d",&t); Addedge(0,i,t);///源点加边 } for(int i=1; i<=d; i++) { scanf("%d",&t); Addedge(f+2*n+i,f+2*n+d+1,t);///汇点加边 } for(int i=1; i<=n; i++) Addedge(f+i,f+n+i,1);///拆点 for(int i=1; i<=n; i++) { scanf("%s",s+1); for(int j=1; j<=f; j++) if(s[j]==‘Y‘) Addedge(j,f+i,1);///顾客与食物加边 } for(int i=1; i<=n; i++) { scanf("%s",s+1); for(int j=1; j<=d; j++) if(s[j]==‘Y‘) Addedge(f+n+i,f+2*n+j,1);///顾客与饮料加边 } printf("%d\n",Dinic_flow()); } return 0; }
学长模板的链接：http://m.blog.csdn.net/article/details?id=30030439
模板：
#include<cstdio> #include<iostream> using namespace std; const int oo=1e9; const int mm=111111; const int mn=999; int node,src,dest,edge; int ver[mm],flow[mm],next[mm]; int head[mn],work[mn],dis[mn],q[mn]; void prepare(int _node,int _src,int _dest) ///node是结点总数 { node=_node,src=http://www.mamicode.com/_src,dest=_dest; for(int i=0; i<node; ++i)head[i]=-1; edge=0; } void addedge(int u,int v,int c) { ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++; ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++; } bool Dinic_bfs() { int i,u,v,l,r=0; for(i=0; i<node; ++i)dis[i]=-1; dis[q[r++]=src]=0; for(l=0; l<r; ++l) for(i=head[u=q[l]]; i>=0; i=next[i]) if(flow[i]&&dis[v=ver[i]]<0) { dis[q[r++]=v]=dis[u]+1; if(v==dest)return 1; } return 0; } int Dinic_dfs(int u,int exp) { if(u==dest)return exp; for(int &i=work[u],v,tmp; i>=0; i=next[i]) if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0) { flow[i]-=tmp; flow[i^1]+=tmp; return tmp; } return 0; } int Dinic_flow() { int i,ret=0,delta; while(Dinic_bfs()) { for(i=0; i<node; ++i)work[i]=head[i]; while(delta=Dinic_dfs(src,oo))ret+=delta; } return ret; }
ISAP模板：
#include <cstdio> #include <cstring> using namespace std; const int MAXN = 2010; const int MAXM = 800000; // ISAP struct edge { int t, f; edge *p, *r; } T[MAXM], *H[MAXN], *I[MAXN], *P[MAXN]; int C; int G[MAXN], D[MAXN], L[MAXN]; inline void adde(const int a, const int b, const int c) { edge *e1 = T + C++; edge *e2 = T + C++; e1->t = b; e1->f = c; e1->p = H[a]; e1->r = e2; H[a] = e1; e2->t = a; e2->f = 0; e2->p = H[b]; e2->r = e1; H[b] = e2; } inline int isap(const int cnt, const int src, const int snk) { int maxf = 0; int curf = 0x3f3f3f3f; int u = src, v; edge *e; memcpy(I, H, sizeof(H)); memset(G, 0, sizeof(G)); memset(D, 0, sizeof(D)); G[0] = cnt; while (D[src] < cnt) { L[u] = curf; for (e = I[u]; e; e = e->p) { v = e->t; if (e->f > 0 && D[u] == D[v] + 1) { I[u] = P[v] = e; if (e->f < curf) curf = e->f; u = v; if (u == snk) { maxf += curf; while (u != src) { P[u]->f -= curf; P[u]->r->f += curf; u = P[u]->r->t; } curf = 0x3f3f3f3f; } break; } } if (e) continue; if (!--G[D[u]]) break; int mind = cnt - 1; for (e = H[u]; e; e = e->p) if (e->f > 0 && D[e->t] < mind) { I[u] = e; mind = D[e->t]; } ++G[D[u] = mind + 1]; if (u != src) { u = P[u]->r->t; curf = L[u]; } } return maxf; } int N, M; bool V[500]; int main() { int tt, a, b, c, ss, cnt; scanf("%d", &tt); for (int tc = 1; tc <= tt; ++tc) { memset(V, false, sizeof(V)); memset(H, 0, sizeof(H)); ss = 0; C = 0; scanf("%d%d", &N, &M); cnt = N + 2; for (int i = 0; i < N; ++i) { scanf("%d%d%d", &a, &b, &c); adde(2004, i, a); for (int j = b - 1; j < c; ++j) { adde(i, j + 1000, 1); if (!V[j]) { adde(j + 1000, 2005, M); V[j] = true; ++cnt; } } ss += a; } if (isap(cnt, 2004, 2005) == ss) printf("Case %d: Yes\n\n", tc); else printf("Case %d: No\n\n", tc); } return 0; }
hdu4292 Food 最大流模板题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。