最大网络流算法

#include
#include
#include
#includeusing namespace std;
const int maxn=100;
const int INF=9999999;
int g[maxn][maxn];//残余网络，初始值为最大流量
int f[maxn][maxn];//实流网络，初始值都是零
int pre[maxn];//存储前驱节点
bool vis[maxn];//判断是否访问过
int n,m;
bool bfs(int s,int t)
{
    memset(pre,-1,sizeof(pre));
    memset(vis,false,sizeof(vis));
    vis[s]=true;
    queueint> que;
    que.push(s);
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        for(int i=1;i)
        {
            if(!vis[i]&&g[now][i]>0)//g[now][i]>0这个条件保证了bfs不会重复搜索 
            {
                vis[i]=true;
                pre[i]=now;
                if(i==t)    return true;
                que.push(i);
            }
        }
    }
    return false;
}
int EK(int s,int t)
{
    int v,w,d,maxflow;
    maxflow=0;
    while(bfs(s,t))
    {
        d=INF;
        v=t;
        while(v!=s)
        {
            w=pre[v];
            if(d>g[w][v])    d=g[w][v];
            v=w;
        }
        maxflow+=d;
        v=t;
        while(v!=s)
        {
            w=pre[v];
            g[w][v]-=d;
            g[v][w]+=d;
            if(f[v][w]>0)
            f[v][w]-=d;
            else
            f[w][w]+=d;
            v=w;
        }
    }
    return maxflow;
}
int main()
{
    int u,v,w;
    cin>>n>>m;
    memset(g,0,sizeof(g));
    memset(f,0,sizeof(f));
    for(int i=1;i)
    {
        cin>>u>>v>>w;
        g[u][v]+=w;
    }
    cout1,n)endl;
    return 0;
}