Drainage Ditches - poj 1273（网络流模板）
生活随笔
收集整理的這篇文章主要介紹了
Drainage Ditches - poj 1273（网络流模板）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題意：1是源點，m是匯點，求出來最大流量，沒什么好說的就是練習最大流的模板題
**************************************************************
?
先用Edmonds-Karp的算法做一下試試吧
重邊貢獻了 1W，要加上所有的重邊才算是兩點間最大流量
***********************************************************************************************************************
/************************************//**?使用Edmonds-Karp?最短增廣路算法*/
/**?鄰接矩陣實現???????????????????*/
/**?2015/8/7/9:39???????????????????*/
/************************************/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using?namespace?std;
const?int?MAXN?=?205;
const?int?oo?=?1e9+7;
///1是源點，M是匯點，N條邊
int?G[MAXN][MAXN],?M,?N;
int?pre[MAXN];///記錄每個點的前驅，也就是父節點
bool?used[MAXN];
///s代表源點，e代表匯點,可以到達匯返回true，否則返回false
bool?BFS(int?s,?int?e)
{
????memset(used,?false,?sizeof(used));
????queue<int>?Q;
????Q.push(s);
????used[s]?=?true;
????while(Q.size())
????{
????????s?=?Q.front();Q.pop();
????????if(s?==?e)?return?true;
????????for(int?i=1;?i<=M;?i++)
????????{
????????????if(G[s][i]?&&?!used[i])
????????????{
????????????????pre[i]?=?s;
????????????????used[i]?=?true;
????????????????Q.push(i);
????????????}
????????}
????}
????return?false;
}
int?Karp(int?s,?int?e)
{
????int?MaxFlow?=?0;
????while(?BFS(s,?e)?==?true?)
????{///如果有增量
????????int?MinFlow?=?oo,?v;
????????v?=?e;
????????while(v?!=?s)
????????{///求出來路徑上最小流量
????????????MinFlow?=?min(MinFlow,?G[pre[v]][v]);
????????????v?=?pre[v];
????????}
????????MaxFlow?+=?MinFlow;
????????v?=?e;
????????while(v?!=?s)
????????{///邊上的所有點減去最小流量，反邊增加流量
????????????G[pre[v]][v]?-=?MinFlow;
????????????G[v][pre[v]]?+=?MinFlow;
????????????v?=?pre[v];
????????}
????}
????return?MaxFlow;
}
int?main()
{
????while(scanf("%d%d",?&N,?&M)?!=?EOF)
????{
????????int?i,?u,?v,?c;
????????memset(G,?false,?sizeof(G));
????????for(i=1;?i<=N;?i++)
????????{
????????????scanf("%d%d%d",?&u,?&v,?&c);
????????????G[u][v]?+=?c;///有重邊，兩點間應該算上所有邊
????????}
????????printf("%d\n",?Karp(1,?M));
????}
????return?0;
} View Code
?
鄰接表實現
***********************************************************************************************************************
/************************************////?使用Edmonds-Karp?最短增廣路算法
///?鄰接表實現
///?2015年8月7日10:13:55
/************************************/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using?namespace?std;
const?int?MAXN?=?205;
const?int?oo?=?1e9+7;
struct?Edge{int?u,?v,?Flow,?next;}e[MAXN<<1];
int?Head[MAXN],?cnt;
int?pre[MAXN],?used[MAXN];
void?InIt()
{
????memset(Head,?-1,?sizeof(Head));
????cnt?=?0;
}
void?AddEdge(int?u,?int?v,?int?Flow)
{
????e[cnt].u?=?u;
????e[cnt].v?=?v;
????e[cnt].Flow?=?Flow;
????e[cnt].next?=?Head[u];
????Head[u]?=?cnt++;
}
bool?BFS(int?s,?int?End)
{
????memset(used,?false,?sizeof(used));
????memset(pre,?-1,?sizeof(pre));
????queue<int>?Q;
????Q.push(s);
????used[s]?=?true;
????while(Q.size())
????{
????????s?=?Q.front();Q.pop();
????????if(s?==?End)return?true;
????????for(int?i=Head[s];?i!=-1;?i=e[i].next)
????????{
????????????if(e[i].Flow?&&?used[e[i].v]?==?false)
????????????{
????????????????used[e[i].v]?=?true;
????????????????pre[e[i].v]?=?i;///記錄的是上面的邊的位置
????????????????Q.push(e[i].v);
????????????}
????????}
????}
????return?false;
}
int?Karp(int?s,?int?End)
{
????int?MaxFlow?=?0;
????while(BFS(s,?End)?==?true)
????{
????????int?MinFlow?=?oo,?v;
????????v?=?pre[End];
????????while(v?!=?-1)
????????{
????????????MinFlow?=?min(MinFlow,?e[v].Flow);
????????????v?=?pre[e[v].u];///上個點來的位置
????????}
????????MaxFlow?+=?MinFlow;
????????v?=?pre[End];
????????while(v?!=?-1)
????????{
????????????e[v].Flow?-=?MinFlow;
????????????e[v^1].Flow?+=?MinFlow;
????????????v?=?pre[e[v].u];
????????}
????}
????return?MaxFlow;
}
int?main()
{
????int?N,?M;
????while(scanf("%d%d",?&N,?&M)?!=?EOF)
????{
????????int?i,?u,?v,?Flow;
????????InIt();
????????for(i=1;?i<=N;?i++)
????????{
????????????scanf("%d%d%d",?&u,?&v,?&Flow);
????????????AddEdge(u,?v,?Flow);
????????????AddEdge(v,?u,?0);///先添加一條反邊的流量是0
????????}
????????printf("%d\n",?Karp(1,?M));
????}
????return?0;
} code
?
Dinic實現?
************************************************************************************************************************
#include<stdio.h>#include<string.h>
#include<queue>
using?namespace?std;
const?int?MAXN?=?205;
const?int?oo?=?1e9+7;
struct?Edge{int?u,?v,?flow,?next;}edge[MAXN*MAXN];
int?Head[MAXN],?cnt;
int?layer[MAXN];///分層
int?Start,?End;///源點匯點
void?AddEdge(int?u,?int?v,?int?flow)
{
????edge[cnt].u?=?u;
????edge[cnt].v?=?v;
????edge[cnt].flow?=?flow;
????edge[cnt].next?=?Head[u];
????Head[u]?=?cnt++;
}
bool?BfsLayer()///使用廣搜進行分層
{
????bool?used[MAXN]={0};queue<int>?Q;
????memset(layer,?-1,?sizeof(layer));
????Q.push(Start);
????used[Start]?=?true;
????layer[Start]?=?0;
????while(Q.size())
????{
????????int?s?=?Q.front();Q.pop();
????????if(s?==?End)return?true;
????????for(int?i=Head[s];?i!=-1;?i=edge[i].next)
????????{
????????????int?v?=?edge[i].v;
????????????if(edge[i].flow?&&?!used[v])
????????????{
????????????????used[v]?=?true;
????????????????layer[v]?=?layer[s]?+?1;
????????????????Q.push(v);
????????????}
????????}
????}
????return?false;
}
int?dfs(int?u,?int?MaxFlow)
{///MaxFlow?記錄的是這條路徑上能經過的最大流量
????if(u?==?End)return?MaxFlow;
????int?uFlow?=?0;///這個點最多能經過多少流量
????for(int?i=Head[u];?i!=-1;?i=edge[i].next)
????{
????????int?v?=?edge[i].v,?flow?=?edge[i].flow;
????????if(layer[v]-1?==?layer[u]?&&?flow)
????????{
????????????flow?=?min(MaxFlow-uFlow,?flow);
????????????flow?=?dfs(v,?flow);
????????????edge[i].flow?-=?flow;
????????????edge[i^1].flow?+=?flow;
????????????uFlow?+=?flow;
????????????if(uFlow?==?MaxFlow)
????????????????break;///已經等于最大流量的時候注意結束
????????}
????}
????return?uFlow;
}
int?Dinic()///用dinic算法求最大流
{
????int?MaxFlow?=?0;
????while(BfsLayer()?==?true)
????{
????????MaxFlow?+=?dfs(Start,?oo);
????}
????return?MaxFlow;
}
int?main()
{
????int?N,?M;
????while(scanf("%d%d",?&N,?&M)?!=?EOF)
????{
????????int?i,?u,?v,?flow;
????????Start?=?1,?End?=?M,?cnt?=?0;
????????memset(Head,?-1,?sizeof(Head));
????????for(i=1;?i<=N;?i++)
????????{
????????????scanf("%d%d%d",?&u,?&v,?&flow);
????????????AddEdge(u,?v,?flow);
????????????AddEdge(v,?u,?0);
????????}
????????printf("%d\n",?Dinic());
????}
????return?0;
} View Code
?
SAP實現
*************************************************************************************************************************
#include<stdio.h>#include<string.h>
#include<queue>
using?namespace?std;
const?int?MAXN?=?205;
const?int?oo?=?1e9+7;
struct?Edge{int?u,?v,?flow,?next;}edge[MAXN*MAXN];
int?Head[MAXN],?cnt;
int?Layer[MAXN];///分層
int?start,?End;///源點匯點
int?cur[MAXN],?Stack[MAXN],gap[MAXN];
int?sumV;///節點的總個數
void?AddEdge(int?u,?int?v,?int?flow)
{
????edge[cnt].u?=?u;
????edge[cnt].v?=?v;
????edge[cnt].flow?=?flow;
????edge[cnt].next?=?Head[u];
????Head[u]?=?cnt++;
}
void?BFS()
{
????memset(Layer,?-1,?sizeof(Layer));
????memset(gap,?0,?sizeof(gap));
????queue<int>?Q;
????Q.push(End);
????Layer[End]?=?0,?gap[0]?=?1;
????while(Q.size())
????{
????????int?u?=?Q.front();
????????Q.pop();
????????for(int?j=Head[u];?j!=-1;?j=edge[j].next)
????????{
????????????int?v?=?edge[j].v;
????????????if(Layer[v]?==?-1)
????????????{
????????????????Layer[v]?=?Layer[u]?+?1;
????????????????gap[Layer[v]]++;
????????????????Q.push(v);
????????????}
????????}
????}
}
int?SAP()
{
????int?j,?top=0,?u?=?start,?MaxFlow=0;
????BFS();
????memcpy(cur,?Head,?sizeof(Head));
????while(Layer[start]?<?sumV)
????{///源點的層次小于總結點數,匯點是0層
????????if(u?==?End)
????????{
????????????int?MinFlow?=?oo,?location;///記錄下最小流量邊的位置，出棧時候用
????????????for(j=0;?j<top;?j++)
????????????{
????????????????int?i?=?Stack[j];
????????????????if(MinFlow?>?edge[i].flow)
????????????????{
????????????????????MinFlow?=?edge[i].flow;
????????????????????location?=?j;
????????????????}
????????????}
????????????for(j=0;?j<top;?j++)
????????????{///所有的邊減去路徑上的最小流量
????????????????int?i?=?Stack[j];
????????????????edge[i].flow?-=?MinFlow;
????????????????edge[i^1].flow?+=?MinFlow;
????????????}
????????????MaxFlow?+=?MinFlow;
????????????top?=?location;///退棧
????????????u?=?edge[Stack[top]].u;
????????}
????????else?if(gap[Layer[u]-1]?==?0)
????????????break;///u所在的層下面的層沒有了，出現了斷層，也就沒有了可行弧
????????for(j=cur[u];?j!=-1;?j=edge[j].next)
????????{///如果u有可行弧就停止
????????????if(Layer[u]==Layer[edge[j].v]+1?&&?edge[j].flow)
????????????????break;
????????}
????????if(j?!=?-1)
????????{///找到了可行弧
????????????cur[u]?=?j;///u點的可行弧是j
????????????Stack[top++]?=?j;///記錄下這條邊
????????????u?=?edge[j].v;
????????}
????????else
????????{///沒有找到可行弧，修改標號
????????????int?MinIndex?=?sumV;
????????????for(j=Head[u];?j!=-1;?j=edge[j].next)
????????????{///查找與u相連的最小的層是多少
????????????????if(edge[j].flow?&&?MinIndex?>?Layer[edge[j].v])
????????????????{///記錄下這條可行弧,下次可以直接訪問這條邊
????????????????????MinIndex?=?Layer[edge[j].v];
????????????????????cur[u]?=?j;
????????????????}
????????????}
????????????gap[Layer[u]]?-=?1;///u改變層，所以u原來所在層的點數減去1
????????????Layer[u]?=?MinIndex?+?1;
????????????gap[Layer[u]]?+=?1;
????????????if(u?!=?start)
????????????{///返回上一層
????????????????u?=?edge[Stack[--top]].u;
????????????}
????????}
????}
????return?MaxFlow;
}
int?main()
{
????int?N,?M;
????while(scanf("%d%d",?&N,?&M)?!=?EOF)
????{
????????int?i,?u,?v,?flow;
????????sumV?=?M;
????????start?=?1,?End?=?M,?cnt?=?0;
????????memset(Head,?-1,?sizeof(Head));
????????for(i=1;?i<=N;?i++)
????????{
????????????scanf("%d%d%d",?&u,?&v,?&flow);
????????????AddEdge(u,?v,?flow);
????????????AddEdge(v,?u,?0);
????????}
????????printf("%d\n",?SAP());
????}
????return?0;
} View Code
轉載于:https://www.cnblogs.com/liuxin13/p/4709956.html
總結
以上是生活随笔為你收集整理的Drainage Ditches - poj 1273（网络流模板）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 做梦梦到被僵尸包围是什么征兆
- 下一篇： 梦到南瓜豆角是什么意思