HDU - 3549 Flow Problem （Dinic模板）

传送门：HDU - 3549

题目描述

Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.

输入描述

The first line of input contains an integer T, denoting the number of test cases.
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)

输出描述

For each test cases, you should output the maximum flow from source 1 to sink N.

思路分析

Dinic模板

样例输入

2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1

样例输出

Case 1: 1
Case 2: 2

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1005,M=100005;

struct node {
    int v,w,next;
} e[M];

int head[N],dep[N],cnt=1;
int n,m;

void add(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

bool bfs(int s,int t) {
    queue<int>q;
    mem(dep,0); 
    dep[s]=1;  
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u]; i ; i=e[i].next) {
            int v=e[i].v;
            int w=e[i].w;
            if(w && !dep[v]) { 
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }

    return dep[t];
}

int dfs(int u,int f,int t) {
    int fl=0;
    if(u==t)
        return f;
    for(int i=head[u]; i && f ; i=e[i].next) {
        int v=e[i].v;
        if(dep[v]==dep[u]+1 && e[i].w) { 
            int nx=dfs(v,min(f,e[i].w),t);
            e[i].w-=nx;
            e[i^1].w+=nx;
            f-=nx;
            fl+=nx;
        }
    }
    if(!fl)
        dep[u]=-2;
    return fl;

}

int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t))
        ans+=dfs(s,INF,t); 
    return ans;
}



int main() {
    int t;
    scanf("%d",&t);
    for(int T=1; T<=t; T++) {
        cnt=1;
        mem(head,0);
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,0);//如果是无向图就是初始流量，有向图是0
        }
        printf("Case %d: %d\n",T,dinic(1,n));

    }

    return 0;
}