最大流dinic模板 poj1273

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

Source

USACO 93

一道dinic的模板题。主要是熟悉一下dinic的思想，bfs求出层次图（即到源点的最小边个数），用dfs进行增广。当前弧优化指的是，因为dfs默认是从第一个边开始的，但是如果用一个cur把上一次循环到的边记录下来，可以大大提高效率。关于增广的问题，代码注释写的很清楚了。

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <cstring>
#include <string.h>
#include <stdio.h>
#include <algorithm>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 99999999
const int maxn=500;
struct Edge
{
    int from, to;
    int flow;       //流量
    Edge(int u, int v, int f): from(u), to(v), flow(f) {}
};
int n, m;
int s, t;
vector<Edge> edges;//边数的两倍
vector<int> G[maxn];//G[i][j]表示节点i的第j条边在edges数组中的序号
int dis[maxn];//从起点s到i的距离
int cur[maxn];//当前弧下标

void init(int n)
{
    for(int i=0; i<n; i++) G[i].clear();
    edges.clear();
}

void add_edge(int from, int to, int flow)
{
    edges.push_back(Edge(from,to,flow));
    edges.push_back(Edge(to,from,0));
    int sz = edges.size();
    G[from].push_back(sz-2);
    G[to].push_back(sz-1);
}

bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i=0; i<G[u].size(); i++)
        {
            Edge &e = edges[G[u][i]];
            if(dis[e.to]==-1 && e.flow>0)  //有余量且没有分过层
            {
                dis[e.to] = dis[u]+1;
                q.push(e.to);
            }
        }
    }
    if(dis[t]==-1)      //如果汇点没有被分层过说明到不了汇点
        return false;
    return true;
}

int dfs(int x, int a) //当前节点x，源点出发余量最小的弧的剩余容量a，函数返回本次增广的流量,返回0表示无法增广
{
    if(x==t) return a;  //如果走到了汇点，返回此时余量，即增广的流量
    int f;
    for(int &i=cur[x]; i<G[x].size(); i++)  //i 加上引用，进行当前弧优化，避免对没有用的路径进行多次检查
    {
        Edge &e = edges[G[x][i]];            //下面if的前两句是说，图依然联通且到达了下一层
        if(dis[x]+1==dis[e.to] && e.flow>0 && (f=dfs(e.to,min(a, e.flow)))>0)     //dfs就是求增广路，即f>0可以到汇点
        {
            e.flow -= f;                  //正向流量减少
            edges[G[x][i]^1].flow += f;   //逆向流量增加
            return f;                    //返回本次增广的流量
        }
    }
    return 0;
}

int dinic(int s, int t)
{
    int ans=0;
    while(bfs())
    {
        memset(cur,0,sizeof(cur));
        int f;
        while(f = dfs(s,INF)) ans += f;   //一次bfs可以进行多次增广
    }
    return ans;
}

int main()
{
    int n;
    while(~scanf("%d %d",&n,&m))
    {
        int x,y,flow;
        init(m);
        s=1,t=m;
        for(int i=1; i<=n; i++)
        {
            scanf("%d %d %d",&x,&y,&flow);
            add_edge(x,y,flow);
        }
        int ans=dinic(1,m);
        printf("%d
",ans);
    }
    return 0;
}

View Code