学步园

最大流的入门题，第一次写了下ek算法，用了邻接矩阵。

EK算法的复杂度为O(n*m^2)

代码：

//EK算法求最大流问题二维数组实现
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#define INF 10000
#define maxn 205
using namespace std;
int n,m;
int path[maxn][maxn],pre[maxn],flow[maxn];
int vis[maxn];
int min(int x,int y)
{
    return x<y?x:y;
}
int bfs()
{
    memset(pre,-1,sizeof(pre));
    memset(flow,INF,sizeof(flow));
    memset(vis,0,sizeof(vis));
    queue<int> q;

    int start=1;
    vis[1]=1;

    //pre[start]=1;
    q.push(start);

    int u;
    while(!q.empty())
    {
        u=q.front();
        q.pop();

        if(u==m) break;

        for(int i=2;i<=m;i++)
        {
            if(path[u][i]!=0&&vis[i]==0)
            {
                pre[i]=u;
                vis[i]=1;
                flow[i]=min(flow[u],path[u][i]);
                q.push(i);
            }
        }
    }
    //cout<<flow[m]<<endl;
    if(vis[m]==0)
    return -1;
    else
    return flow[m];//找到增广路
}
int ek()
{
    int nowflow,maxflow=0;
    while((nowflow=bfs())!=-1)//剩余网络中是否有增广路
    {
        //cout<<nowflow<<endl;
        maxflow+=nowflow;
        int v=m;
        while(v!=1)
        {
            int u=pre[v];
            path[u][v]-=nowflow;
            path[v][u]+=nowflow;
            v=u;
        }
    }
    return maxflow;
}
int main()
{
    int s,e,v;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(path,0,sizeof(path));
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&s,&e,&v);
            path[s][e]+=v;
        }
        printf("%d\n",ek());
    }
    return 0;
}

dinic算法：复杂度O（n^2*m）

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define inf 0x7fffffff
#define maxn 205
using namespace std;
int s,t,n,m;
int d[maxn];//每个点的层次
int flow[maxn][maxn];
int min(int x,int y)
{
    return x<y?x:y;
}
int bfs()
{
    memset(d,-1,sizeof(d));
    d[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(flow[u][i]>0&&d[i]==-1)
            {
                d[i]=d[u]+1;
                q.push(i);
            }
        }
    }
    return d[t]!=-1;
}
int dfs(int u,int sum)//u及流到u的最大流
{
    if(u==t) return sum;
    int ret=0,k;
    for(int i=1;i<=n;i++)
    {
        if(flow[u][i]>0&&d[u]+1==d[i])
        {
            if(k=dfs(i,min(flow[u][i],sum-ret)))//求从i到t的最大流（流到i的最大流）
            {
                flow[u][i]-=k;
                flow[i][u]+=k;
                ret+=k;
            }
        }
    }
    return ret;
}
int dinic()
{
    int w=0;
    while(bfs())//如果能建层
    {
        w+=dfs(1,inf);//找所有的增广路
    }
    return w;
}
int main()
{
    int u,v,c;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        s=1,t=n;
        memset(flow,0,sizeof(flow));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&c);
            flow[u][v]+=c;
        }
        printf("%d\n",dinic());
    }
    return 0;
}