网络流总结

2017-12-08 23:21:09


两个板子

【模板】最大流

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define inf 1000000000
const int _ = 100005;
struct edge{int to,next,w;}a[_<<1];
int n,m,s,t,head[_],cnt=1,cur[_],dep[_],ans;
queue<int>Q;
int gi()
{
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w?x:-x;
}
void link(int u,int v,int w)
{
    a[++cnt]=(edge){v,head[u],w};
    head[u]=cnt;
    a[++cnt]=(edge){u,head[v],w};
    head[v]=cnt; 
}
int bfs()
{
    memset(dep,0,sizeof(dep));
    Q.push(s);dep[s]=1;
    while (!Q.empty())
    {
        int u=Q.front();Q.pop();
        for (int e=head[u];e;e=a[e].next)
            if (!dep[a[e].to]&&a[e].w)
                dep[a[e].to]=dep[u]+1,Q.push(a[e].to);
    }
    return dep[t];
}
int dfs(int u,int flow)
{
    if (u==t)
        return flow;
    for (int &e=cur[u];e;e=a[e].next)
        if (dep[a[e].to]==dep[u]+1&&a[e].w)
        {
            int temp=dfs(a[e].to,min(a[e].w,flow));
            if (temp) {a[e].w-=temp;a[e^1].w+=temp;return temp;}
        }
    return 0;
}
int main()
{
    n=gi();m=gi();
    /*
        中间是建边的过程
    */
    while (bfs())
    {
        for (int i=1;i<=n;i++) cur[i]=head[i];
        while (int temp=dfs(s,inf)) ans+=temp;
    }
    printf("%d\n",ans);
    return 0;
}

【模板】最小费用最大流

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define inf 1000000000
const int _ = 100005;
struct edge{int to,next,w,cost;}a[_<<1];
int n,m,s,t,head[_],cnt=1,dis[_],vis[_],pe[_],pv[_],ans;
queue<int>Q;
int gi()
{
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
void link(int u,int v,int w,int cost)
{
    a[++cnt]=(edge){v,head[u],w,cost};
    head[u]=cnt;
    a[++cnt]=(edge){u,head[v],0,-cost};
    head[v]=cnt;
}
bool spfa()
{
    memset(dis,63,sizeof(dis));
    dis[s]=0;Q.push(s);
    while (!Q.empty())
    {
        int u=Q.front();Q.pop();
        for (int e=head[u];e;e=a[e].next)
        {
            int v=a[e].to;
            if (a[e].w&&dis[v]>dis[u]+a[e].cost)
            {
                dis[v]=dis[u]+a[e].cost;
                pe[v]=e;pv[v]=u;
                if (!vis[v]) vis[v]=1,Q.push(v);
            }
        }
        vis[u]=0;
    }
    return dis[t]<dis[0];
}
int main()
{
    n=gi();m=gi();
    /*
        中间是建边的过程
    */
    while (spfa())
    {
        int sum=inf;
        for (int i=t;i!=s;i=pv[i])
            sum=min(sum,a[pe[i]].w);
        ans+=dis[t];
        for (int i=t;i!=s;i=pv[i])
            a[pe[i]].w-=sum,a[pe[i]^1].w+=sum;
    }
    printf("%d\n",ans);
    return 0;
}

技巧总结

单点限流量

拆点,每个点拆成出点和入点,连边的时候从出点连向入点。

连续转移问题

也就是说状态会持续转移,从一个点到一个点再到另一个点。经典例题

https://www.luogu.org/problemnew/show/1251

餐巾计划问题(网络流24题10)

我们换个方式理解,因为每个点通过的流量是限制了的,所以可以认为每个点都是源点,也都是汇点。拆成两个点,s向每个“源点”连一条容量为指定数量的边,每个“汇点”向t同样连一条容量为指定数量的边,然后就是最小费用流了。

最大收益问题

最大收益不好转化为最大流,但转化为最小割又出现了问最大而求最小矛盾。这里转化一下思想,其实求最大收益,就是求最小损失。我们先假设所有能赚到的收益都赚到了,然后就是最小化自己的损失。

同样以一道题来讲。https://www.luogu.org/problemnew/show/P2762

太空飞行计划问题(网络流24题2)

我们要选择一些实验并购买一些实验所需仪器,使总利润最大。如果不转化模型的话,既赚钱又花钱就很难处理。我们先假设我们已经拿到了所有的实验利润,然后就需要最小化损失,这里的损失可能是花了成本,也可能是没有得到收益,通过最小割问题求解。

一些图论的相关术语

最小顶点覆盖

是指用最少数量(或最小权值和)的顶点去覆盖所有的边。

最小顶点覆盖NP-hard,但是如果图是一个二分图,可以用最小割跑。怎么跑自己想嘿嘿嘿。

最大独立集

是指在图中选出最多数量(或权值和最大)的点使得任两个点不直接相邻。

公式:最大独立集=sum-最小顶点覆盖

https://www.luogu.org/problemnew/show/2774

https://www.luogu.org/problemnew/show/3355

方格取数问题、骑士共存问题

最大独立集转最小顶点覆盖转二分图最小割转最大流即可。