HDU 3549 Flow Problem【网络流入门题】

没找到比较好的博客介绍网络流，可以看下白书（电子书的224页）

Edmonds-Karp（EK）算法  O(V*E*E) 124ms

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define INF 0x7FFFFFFF
#define INT_MIN -(1<<31)
#define eps 10^(-6)
#define Q_CIN ios::sync_with_stdio(false)
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REV( i , n ) for ( int i = n - 1 ; i >= 0 ; -- i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof (a) )
#define RE freopen("in.txt","r",stdin)
#define WE freopen("out.txt","w",stdout)
#define NMAX 1002
#define min(a,b) ((a)>(b)?(b):(a))
#define Dian_NAX 21
int flow[Dian_NAX][Dian_NAX];   //边实际流量
int cap[Dian_NAX][Dian_NAX];    //边容量
int pre[NMAX];  //增广路径
int res[NMAX];  //残余网络

int n;          //点
int EK(int s,int t)
{
    queueq;
    int ans = 0;
    CLR(flow,0);
    while(true)
    {
        CLR(res,0);
        res[s] = INF; //源点无限大
        q.push(s);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int v=1;v<=n;v++)
                if(!res[v] && flow[u][v] < cap[u][v])
                {
                    pre[v] = u;
                    q.push(v);
                    res[v] = min(res[u],cap[u][v] - flow[u][v]);
                }
        }
        if(res[t] == 0) //找不到增广路就退出
            break;
        for(int u = t;u != s; u=pre[u])
        {
            flow[pre[u]][u] += res[t];
            flow[u][pre[u]] -= res[t];      //反向边
        }
        ans += res[t];
    }
    return ans;
}
int main()
{
    int a,b,c,t,m;
    int test = 1;
  //  RE;
    scanf("%d",&t);
    while(t--)
    {
        CLR(cap,0);
        scanf("%d%d",&n,&m);
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            cap[a][b] +=c;
        }
        printf("Case %d: %d\n",test++,EK(1,n));
    }
    return 0;
}

Dinic 124ms

#include 
#include 
#include 
using namespace std;
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define CLR( a , x ) memset ( a , x , sizeof (a) );
#define RE freopen("1.in","r",stdin);
#define WE freopen("output.txt","w",stdout);
#define debug(x) cout<<#x<<":"<<(x)<0)
            {
                dis[i]=dis[cur]+1;
                q[tail++]=i;
            }
        }
    }
    if(dis[t]>0)    return 1;
    return 0;   //dis[t]=-1：路不通
}
//dfs为一次增广,s->t
int dfs(int s,int t,int low)//Low为增广路径上的最小流量
{
    int flow=0;
    if(s==t)    return low; //到汇点直接返回目前为止的最小流量
    for(int i=1;i<=n;i++)
    {       //在下一层里找
        if(tab[s][i]>0
           &&dis[i]==dis[s]+1
           &&(flow=dfs(i,t,min(low,tab[s][i]))))
        {
            tab[s][i]-=flow;    //不断的减流量
            tab[i][s]+=flow;
            return flow;        //能到汇点
        }
    }
    return 0;
}

int main() {
//    RE
    int a,b,c,t;
    scanf("%d",&t);
    for(int te=1;te<=t;te++)
    {
        scanf("%d%d",&n,&m);
        CLR(tab,0); //流量初始化为0
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            tab[a][b]+=c;
        }
        int ans=0,tans=0;
        while(bfs(1,n))         //直到源点不能到汇点为止
            while(tans=dfs(1,n,0x7FFFFFFF))     //在同一个层次图里尽量找增广路
                ans+=tans;
         printf("Case %d: %d\n",te,ans);
    }
    return 0;
}

邻接表 436MS

#include 
#include 
#include 
#include 
using namespace std;
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define CLR( a , x ) memset ( a , x , sizeof (a) );
#define RE freopen("1.in","r",stdin);
#define WE freopen("output.txt","w",stdout);
#define debug(x) cout<<#x<<":"<<(x)<q;
    q.push(s);
    CLR(dis,-1);
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if( dis[v]<0 && edge[i].w)
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[t]!=-1;
}
int dfs(int s,int t,int low)
{
    int flow;
    if(t==s)   return low;
    for(int i=head[s];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(edge[i].w && (dis[v]==dis[s]+1) &&
            (flow = dfs(v,t,min(low,edge[i].w))))
        {
            edge[i].w -= flow;
            edge[i^1].w += flow;
            return flow;
        }
    }
    return 0;
}
int maxFlow(int s,int t)
{
    int ans=0,tmp;
    while(bfs(s,t))
        while(tmp=dfs(s,t,inf))
            ans+=tmp;
    return ans;
}
int main()
{
    int t,m,n,a,b,c;
//    RE
    scanf("%d",&t);

    for(int te=1;te<=t;te++)
    {
        init();
        scanf("%d%d",&n,&m);
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            addEdge(a,b,c);
        }
        printf("Case %d: %d\n",te,maxFlow(1,n));
    }
    return 0;
}