[hdu3549]Flow Problem(最大流模板题)

解题关键：使用的挑战程序设计竞赛上的模板，第一道网络流题目，效率比较低，且用不习惯的vector来建图。

看到网上其他人说此题有重边，需要注意下，此问题只在邻接矩阵建图时会出问题，邻接表不会存在的，也体现了邻接表的优越性？

edge结构体的第三个变量为from的下标。

模板一：

#include<bits/stdc++.h>
#define MAX_V 17
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,s,t;
struct edge{
    int to,cap,rev;
};
vector<edge>G[MAX_V];
bool used[MAX_V];
void add_edge(int from,int to,int cap){
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}
int dfs(int v,int t,int f){
    if(v==t)return f;
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
        edge &e=G[v][i];
        if(!used[e.to]&&e.cap>0){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s,int t){
    int flow=0;
    while(1){
        memset(used,0,sizeof used);
        int f=dfs(s,t,inf);
        if(f==0) return flow;
        flow+=f;
    }
    return flow;
}

int main(){
    int T,u,v,f;
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++){
        memset(G,0,sizeof G);
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&f);
            add_edge(u,v,f);
        }
        s=1,t=n;
        int ans=max_flow(s,t);
        printf("Case %d: %d
",ca,ans);
    }
    return 0;
}

 模板二：dinic，187ms，比第一个快，在层次图上进行增广，且进行了当前弧优化。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX_V 17
using namespace std;
typedef long long ll;
struct edge{int to,cap,rev;};//终点，容量，反向边 
vector<edge>G[MAX_V];
int level[MAX_V],iter[MAX_V];
int n,m,s,t;
void add_edge(int from,int to,int cap){
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s){
    memset(level,-1,sizeof level);
    queue<int>que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v=que.front();que.pop();
        for(int i=0;i<G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v,int t,int f){
    if(v==t) return f;
    for(int &i=iter[v];i<G[v].size();i++){
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s,int t){
    int flow=0;
    while(1){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof iter);
        int f;
        while((f=dfs(s,t,inf))>0){
            flow+=f;
        }
    }
    return flow;
}

int main(){
    int T,u,v,f;
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++){
        memset(G,0,sizeof G);
        memset(iter,0,sizeof iter);
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&f);
            add_edge(u,v,f);
        }
        s=1,t=n;
        int ans=max_flow(s,t);
        printf("Case %d: %d
",ca,ans);
    }
    return 0;
}