首页 > 代码库 > 【网络流最大流】poj3281Dining
【网络流最大流】poj3281Dining
/* EK算法版本的,比较慢哦。。。。。详见下面dinic版本 ----------------------------------------- 题目是网络流最大流的问题 ---------------------------------------- 建图: 关键:拆点 把每个牛拆成两个点,牛作为一个点有流量限制,即每一头牛只能的一份饭。 把牛拆开后,将边的权值赋值为1, ---------------------------------------- 建好图后就可以EK算法最大流了 ---------------------------------------- 建图代码: for(int i=1; i<=f; i++)源点和food相连 g[s][i] = 1; for(int i=1; i<=d; i++)drink和汇点相连 g[i + 2*n + f][t] = 1; for(int i=1; i<=n; i++) { cin>>a>>b; for(int j=1; j<=a; j++) { cin>>food; g[food][f + i] = 1;food和牛相连 } g[f + i][f + i + n] = 1;牛拆点后也要相连 for(int j=1; j<=b; j++) { cin>>drink; g[f + i + n][2*n + f + drink] = 1;牛和drink相连 } } --------------------------------- */ #include <iostream> #include <cstdio> #include <queue> #include <cstring> #define INF 0x3f3f3f3f using namespace std; const int N = 500; int n,f,d; int g[N][N]; int flow[N][N],a[N],p[N]; int s,t; int EK(int s, int t) { queue<int> q; int f = 0; for(;;) { memset(a,0,sizeof(a)); a[s] = INF; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int v=s; v<=t; v++) { if(!a[v] && g[u][v] > flow[u][v]) { p[v] = u; q.push(v); a[v] = min(a[u],g[u][v] - flow[u][v]); } } } if(a[t] == 0) break; for(int u=t; u != s; u=p[u]) { flow[p[u]][u] += a[t]; flow[u][p[u]] -= a[t]; } f += a[t]; } return f; } void init() { int a,b,food,drink; s = 0; t = 2*n + f + d + 1; memset(g,0,sizeof(g)); for(int i=1; i<=f; i++) g[s][i] = 1; for(int i=1; i<=d; i++) g[i + 2*n + f][t] = 1; for(int i=1; i<=n; i++) { cin>>a>>b; for(int j=1; j<=a; j++) { cin>>food; g[food][f + i] = 1; } g[f + i][f + i + n] = 1; for(int j=1; j<=b; j++) { cin>>drink; g[f + i + n][2*n + f + drink] = 1; } } } int main() { //freopen("input.txt","r",stdin); while(scanf("%d%d%d",&n,&f,&d) != EOF) { init(); printf("%d\n",EK(s, t)); } return 0; }
--------------------------------------------------------------------
战斗,毫不退缩;奋斗,永不停歇~~~~~~~~~~~~~~
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。