[caioj 1115] 网络流入门1 --- dinic最大流

【题目描述】

一个有向图， M条有向边和N个点，求点1 到点N的最大流。

【输入格式】
第1行:2个整数M (2 <= M <= 200) 和N (0 <= N <= 200)。（注意给出的格式M N）
下来M行: 每行有三个整数：x,y,c。表示一条从点x到点y的有向边，流量为c (0<= c <= 10,000,000)。
【输出格式】
输出一个整数，即最大流量。
SAMPLE INPUT
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
SAMPLE OUTPUT
50

提供一个理论上可以卡最短路的数据：

【样例输入】
4 4
1 2 10
2 4 5
2 3 20
3 4 10

【样例输出】

10

分析

dinic（LRJ蓝书模版）

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>

#define IL inline
#define INF 0x7f7f7f7f

#define open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define close fclose(stdin); fclose(stdout);

using namespace std;

inline int read()
{
char c=getchar();
int sum=0,k=1;
for(;'0'>c || c>'9';c=getchar())
if(c=='-') k=-1;
for(;'0'<=c && c<='9';c=getchar()) sum=sum*10+c-'0';
return sum*k;
}

struct Edge
{
int from, to, cap, flow;
};

int n, m;
vector<Edge> edge;
vector<int> G[205];
bool vis[205];
int dep[205];
int cur[205];

IL int min_(int x, int y) { return x < y ? x : y; }

IL void add(int u, int v, int c, int k)
{
    edge.push_back((Edge){u, v, c, 0});
    edge.push_back((Edge){v, u, 0, 0});
    G[u].push_back(k);
    G[v].push_back(k|1);
}

IL bool Bfs()
{
memset(vis, 0, sizeof(vis));
queue<int>q;
    dep[1] = 0;
    vis[1] = 1;
    q.push(1);
for(int t = 1, u, v; t;)
    {
        u= q.front(); q.pop(); --t;
for(int i = 0, s = G[u].size(); i < s; ++i)
        {
            Edge &e = edge[G[u][i]];
if(!vis[e.to] && e.cap > e.flow)
            {
                vis[e.to] = 1;
                dep[e.to] = dep[u] + 1;
                q.push(e.to); ++t;
            }
        }
    }
return vis[n];
}

IL int Dfs(int u, int a)
{
if(u == n || !a) return a;
int flow = 0, f;
for(int &i = cur[u], s = G[u].size(); i < s; ++i)
    {
        Edge &e = edge[G[u][i]];
if(dep[u] + 1 == dep[e.to] && (f = Dfs(e.to, min_(a, e.cap - e.flow))) > 0)
        {
            e.flow += f;
            edge[G[u][i] ^ 1].flow -= f;
            flow += f;
            a -= f;
if(!a) break;
        }
    }
return flow;
}

int main()
{
    open("1115");

    m = read(); n = read();

for(int i = 0, u, v, c; i < m; ++i)
    {
        u = read(); v = read(); c = read();
        add(u, v, c, i << 1);
    }

int flow = 0;
for(; Bfs();)
    {
memset(cur, 0, sizeof(cur));
        flow += Dfs(1, INF);
    }

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


    close;
return 0;
}