经典的最大流题POJ1273（网络流裸题）

Drainage Ditches

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions:87219		Accepted: 33916

Description

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input

The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output

For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

Sample Output

50

现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的池塘和所能流过的水量,求水渠中所能流过的水的最大容量.一道基础的最大流题目。

——其他练习题 POJ3436 、

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <bitset>

 #include <cmath>

 #include <cctype>

 #include <iostream>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 #include <sstream>

 #include <iomanip>

 using namespace std;

 typedef long long ll;

 typedef unsigned long long ull;

 const ll inff = 0x3f3f3f3f3f3f3f3f;

 #define FOR(i,a,b) for(int i(a);i<=(b);++i)

 #define FOL(i,a,b) for(int i(a);i>=(b);--i)

 #define REW(a,b) memset(a,b,sizeof(a))

 #define inf int(0x3f3f3f3f)

 #define si(a) scanf("%d",&a)

 #define sl(a) scanf("%I64d",&a)

 #define sd(a) scanf("%lf",&a)

 #define ss(a) scanf("%s",a)

 #define mod ll(998244353)

 #define pb push_back

 #define eps 1e-6

 #define lc d<<1

 #define rc d<<1|1

 #define Pll pair<ll,ll>

 #define P pair<int,int>

 #define pi acos(-1)

 const int N=,M=;

 int head[N],tot,n,m,a,b,c;

 struct node{

 int next,c,to;}e[M];

 struct max_flow{

     int S,T,n;

     int lev[N],q[N],cur[N],f;

     void init(int _s,int _t)

     {

         tot=;S=_s,T=_t,n=T+;

         FOR(i,,n) head[i]=-;

     }

     void add(int a,int b,int c)

     {

         e[tot].next=head[a];

         e[tot].to=b;

         e[tot].c=c;

         head[a]=tot++;

     }

     void Add(int a,int b,int c)

     {

         add(a,b,c);

         add(b,a,);

     }

     int bfs()

     {

         FOR(i,,n) lev[i]=;

         lev[S]=,f=,q[f++]=S;

         FOR(i,,f-)

         {

             int u=q[i];

             for(int i=head[u];i!=-;i=e[i].next)

              if(lev[e[i].to]==&&e[i].c>)

              {

                  int to=e[i].to;

                  lev[to]=lev[u]+;

                  q[f++]=to;

                  if(to==T) return ;

              }

         }

         return ;

     }

     int dfs(int u,int f)

     {

         if(u==T) return f;

         int tag=,c;

         for(int &i=cur[u];i!=-;i=e[i].next)

         {

             int to=e[i].to;

             if(e[i].c>&&lev[to]==lev[u]+)

             {

                 c=dfs(to,min(f-tag,e[i].c));

                 e[i].c-=c;

                 e[i^].c+=c;

                 tag+=c;

                 if(tag==f) return tag;

             }

         }

         return tag;

     }

     int slove()

     {

         int ans=;

         while(bfs())

         {

             FOR(i,,n) cur[i]=head[i];

             ans+=dfs(S,inf);

         }

         return ans;

     }

 }flow;

 int main()

 {

     cin.tie();

     cout.tie();

     while(~scanf("%d%d",&m,&n))

     {

         flow.init(,n);

         while(m--)

         {

             si(a),si(b),si(c);

             flow.Add(a,b,c);

         }

         cout<<flow.slove()<<endl;

     }

     return ;

 }

https://blog.csdn.net/huzhengnan/article/details/7766446

最大流的一些板子

https://blog.csdn.net/wjf_wzzc/article/details/24820525

sap:

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<cstdlib>

 #include<string>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int N=;

 const int M=;

 const int inf=0xfffffff;

 int n,m,cnt;

 struct Edge{

     int v , cap , next;

 } edge[M];

 int head[N],pre[N],d[N],numd[N];//分别为链表的头指针，每个点的前驱，每个点的d值，以及标号为d[i] 的点的个数

 int cur_edge[N];//从每个点出发满足d[i] = d[j] + 1的边的地址 ， 插入边时的计数，源点与汇点

 void addedge(int u,int v,int c){

     edge[cnt].v = v;

     edge[cnt].cap = c;

     edge[cnt].next = head[u];

     head[u] = cnt++;

     edge[cnt].v = u;

     edge[cnt].cap = ;

     edge[cnt].next = head[v];

     head[v] = cnt++;

 }

 void bfs(int s){    //先用广度优先算出每个点的d值

     memset(numd,,sizeof(numd));

     for(int i=; i<=n; i++)

         numd[ d[i] = n ]++;

     d[s] = ;

     numd[n]--;

     numd[]++;

     queue<int> Q;

     Q.push(s);

     while(!Q.empty()){

         int v=Q.front();

         Q.pop();

         int i=head[v];

         while(i != -){

             int u=edge[i].v;

             if(d[u]<n){

                 i=edge[i].next;

                 continue ;

             }

             d[u]=d[v]+;

             numd[n]--;

             numd[d[u]]++;

             Q.push(u);

             i=edge[i].next;

         }

     }

 }

 int SAP(int s,int t){

     for(int i = ; i <= n; i++)

         cur_edge[i] = head[i];   //当前满足d[i] = d[j] + 1的边的为第一条边

     int max_flow=;

     bfs(t);

     int u = s ;//从源点搜一条到汇点的增广路

     while(d[s]<n){//就算所有的点连成一条线源点的d值也是最多是n-1

         if(u == t){//如果找到一条增广路径

             int cur_flow = inf,neck;//找到那条瓶颈边

             for(int from = s; from != t; from = edge[cur_edge[from]].v){

                 if(cur_flow > edge[cur_edge[from]].cap){

                     neck = from;

                     cur_flow = edge[cur_edge[from]].cap;

                 }

             }

             for(int from = s; from != t; from = edge[cur_edge[from]].v){    //修改增广路上的边的容量

                 int tmp = cur_edge[from];

                 edge[tmp].cap -= cur_flow;

                 edge[tmp^].cap += cur_flow;

             }

             max_flow += cur_flow;//累加计算最大流

             u = neck;//下一次搜索直接从瓶颈边的前一个节点搜起

         }

         int i;

         for(i = cur_edge[u]; i != -; i = edge[i].next) //从当前点开始找一条允许弧

             if(edge[i].cap && d[u] == d[edge[i].v]+)//如果找到跳出循环

                 break;

         if(i!=-){//找到一条允许弧

             cur_edge[u] = i;//从点u出发的允许弧的地址

             pre[edge[i].v] = u;//允许弧上下一个点的前驱为u

             u = edge[i].v;//u变成下一个点继续搜直到搜出一条增广路

         }

         else{//如果没有搜到允许弧

             numd[d[u]]--; //d[u]将被修改所以numd[d[u]]减一

             if(!numd[d[u]]) break;  //如果没有点的d值为d[u]则不可能再搜到增广路结束搜索

             cur_edge[u] = head[u];  //当前点的允许弧为第一条边

             int tmp = n;

             for(int j = head[u]; j != -; j = edge[j].next) //搜与u相连的点中d值最小的

                 if(edge[j].cap && tmp > d[edge[j].v])

                     tmp = d[edge[j].v];

             d[u] = tmp+; //修改d[u]

             numd[d[u]]++;

             if(u != s)

                 u = pre[u];//从u的前驱搜，因为从u没有搜到允许弧

         }

     }

     return max_flow;

 }

 inline void pre_init(){

     cnt = ;

     memset(head, -, sizeof head);

 } 

 void mapping(){

     int u, v, w;

     for(int i = ; i <= m; ++i){

         scanf("%d %d %d", &u, &v, &w);

         addedge(u, v, w);

     }

 }

 int main(){

     while(~scanf("%d%d",&m,&n)){

         pre_init();

         mapping();

         int s,t;

         s = ;t = n;

         int ans = SAP(s,t);

         printf("%d\n",ans);

     }

     return ;

 }

dinic:

 //dinic

 #include <algorithm>

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <queue>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 const int maxn = ;

 const int maxm = maxn*maxn;

 struct node{int w; int v, next;} edge[maxm];

 int pre[maxn], rec[maxn], head[maxn], block[maxn];

 int dis[maxn];

 int n, m, no;

 int S, T;

 queue<int> q;

 inline void init(){

     no = ;

     memset(head, -, sizeof head);

 }

 inline void add(int u, int v, int w){

     edge[no].v = v; edge[no].w = w;

     edge[no].next = head[u]; head[u] = no++;

     edge[no].v = u; edge[no].w = ;

     edge[no].next = head[v]; head[v] = no++;

 }

 void reset(int S, int T){

     memset(dis, 0x3f, sizeof dis);

     memset(block, , sizeof block);

     q.push(S); dis[S] = ;

     while(!q.empty()){

         int top = q.front(); q.pop();

         for(int k = head[top]; k != -; k = edge[k].next)

         if(dis[edge[k].v] == inf && edge[k].w)

             dis[edge[k].v] = dis[top]+, q.push(edge[k].v);

     }

 }

 int dinic(int S, int T){

     int ans = , flow = inf;

     int top = S;

     reset(S, T); pre[S] = S;

     while(dis[T] != inf){

         int k, tmp;

         for(k = head[top]; k != -; k = edge[k].next){

             if(edge[k].w && dis[edge[k].v]==dis[top]+ &&

             !block[edge[k].v]) break;

         }

         if(k != -){

             tmp = edge[k].v;

             flow = min(flow, edge[k].w);

             pre[tmp] = top, rec[tmp] = k;

             top = tmp;

             if(top == T){

                 ans += flow; tmp = -;

                 for(; top != S; top = pre[top]){

                     edge[rec[top]].w -= flow;

                     edge[rec[top]^].w += flow;

                     if(!edge[rec[top]].w) tmp = top;

                 }

                 flow = inf;

                 if(tmp != -){

                     top = pre[tmp];

                     for(; top != S; top = pre[top])

                     flow = min(flow, edge[rec[top]].w);

                     top = pre[tmp];

                 }

             }

         }

         else{

             block[top] = ;

             top = pre[top];

             if(block[S]) reset(S, T);

         }

     }

     return ans;

 }

 void mapping(){

     int u, v, w;

     for(int i = ; i <= m; ++i){

         scanf("%d %d %d", &u, &v, &w);

         add(u, v, w);

     }

 }

 int main(){

     while(~scanf("%d %d", &m, &n)){

         S = , T = n;

         init();

         mapping();

         printf("%d\n", dinic(S, T));

     }

     return ;

 }

感谢https://www.cnblogs.com/Asumi/p/9751117.html

【最大流之Dinic算法】POJ1273 【 & 当前弧优化 & 】

https://www.cnblogs.com/DF-yimeng/p/8583698.html

//dinic

#include <algorithm>

#include <iostream>

#include <string.h>

#include <cstdio>

#include <queue>

using namespace std;

const int inf = 0x3f3f3f3f;

const int maxn = ;

const int maxm = maxn*maxn;

struct node

{

    int w;

    int v, next;

} edge[maxm];

int pre[maxn], rec[maxn], head[maxn], block[maxn];

int dis[maxn];

int n, m, no;

int S, T;

queue<int> q;

inline void init()

{

    no = ;

    memset(head, -, sizeof head);

}

inline void add(int u, int v, int w)

{

    edge[no].v = v;

    edge[no].w = w;

    edge[no].next = head[u];

    head[u] = no++;

    edge[no].v = u;

    edge[no].w = ;

    edge[no].next = head[v];

    head[v] = no++;

}

void reset(int S, int T)

{

    memset(dis, 0x3f, sizeof dis);

    memset(block, , sizeof block);

    q.push(S);

    dis[S] = ;

    while(!q.empty())

    {

        int top = q.front();

        q.pop();

        for(int k = head[top]; k != -; k = edge[k].next)        if(dis[edge[k].v] == inf && edge[k].w)            dis[edge[k].v] = dis[top]+, q.push(edge[k].v);

    }

}

int dinic(int S, int T)

{

    int ans = , flow = inf;

    int top = S;

    reset(S, T);

    pre[S] = S;

    while(dis[T] != inf)

    {

        int k, tmp;

        for(k = head[top]; k != -; k = edge[k].next)

        {

            if(edge[k].w && dis[edge[k].v]==dis[top]+ &&             !block[edge[k].v]) break;

        }

        if(k != -)

        {

            tmp = edge[k].v;

            flow = min(flow, edge[k].w);

            pre[tmp] = top, rec[tmp] = k;

            top = tmp;

            if(top == T)

            {

                ans += flow;

                tmp = -;

                for(; top != S; top = pre[top])

                {

                    edge[rec[top]].w -= flow;

                    edge[rec[top]^].w += flow;

                    if(!edge[rec[top]].w) tmp = top;

                }

                flow = inf;

                if(tmp != -)

                {

                    top = pre[tmp];

                    for(; top != S; top = pre[top])                    flow = min(flow, edge[rec[top]].w);

                    top = pre[tmp];

                }

            }

        }

        else

        {

            block[top] = ;

            top = pre[top];

            if(block[S]) reset(S, T);

        }

    }

    return ans;

}

void mapping()

{

    int u, v, w;

    for(int i = ; i <= m; ++i)

    {

        scanf("%d %d %d", &u, &v, &w);

        add(u, v, w);

    }

}

int main()

{

    while(~scanf("%d %d", &m, &n))

    {

        S = , T = n;

        init();

        mapping();

        printf("%d\n", dinic(S, T));

    }

    return ;

}

巴特西

经典的最大流题POJ1273（网络流裸题）

【最大流之Dinic算法】POJ1273 【 & 当前弧优化 & 】

最新文章

热门文章