首页 > 代码库 > 最大流

最大流

2024-08-22 05:30:45   219人阅读

最大流最重要的思想就是反向边，其他的不说了，为什么要有反向边呢？

举个例子，白书上那张图，画一画有奇效。其实每次增广的时候，我们的流到了一个点，然后呢把反向边推回去了，也就是相当于把从那边流过来的流推回去了，为什么这是最优的？你想啊，那个流原来是流向某条边，现在来了一个流，把他替代了，叫这个流回去，当然比以前优了，因为那个流回去之后肯定对答案有贡献。

bfs是找到下一步往哪里走，也是判断。

dinic什么分层图不要管他，其实就是每次找自己能走的邻居，只不过是走一步，分层了。

codevs 1993

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,f,nxt;
}e[10010];
int n,m,cnt=1;
int d[10010],q[10010],g[10010];
inline void Init()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    d[1]=1;
}
inline void link(int u,int v,int c)
{
    e[++cnt].nxt=g[u];
    g[u]=cnt;
    e[cnt].to=v;
    e[cnt].f=c;
}
inline int Min(int x,int y)
{
    return x<y?x:y;
}
inline int read()
{
    int x=0,f=1; char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x*=10;x+=c-‘0‘;c=getchar();}
    return x*f;
}
bool bfs()
{
    Init(); 
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=g[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(e[i].f&&d[v]==inf)
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }    
    return d[n]!=inf;
}
int dfs(int u,int delta)
{
    if(u==n) return delta;
    int ret=0;
    for(int i=g[u];i&&delta;i=e[i].nxt)
    {
        int v=e[i].to;
        if(d[v]==d[u]+1)
        {
            int dd=dfs(v,Min(delta,e[i].f));
            e[i].f-=dd;
            e[i^1].f+=dd;
            delta-=dd;
            ret+=dd;
        }
    }
    return ret;
}
inline void dinic()
{
    int tot=0;
    while(bfs())
    {
        tot+=dfs(1,inf);
    }
    printf("%d",tot);
}
int main()
{
    m=read(); n=read();
    for(int i=1;i<=m;i++)
    {
        int u,v,c; u=read(); v=read(); c=read();
        link(u,v,c); link(v,u,0);
    }
    dinic();
    return 0;
}

 

最大流


联系
我们