上下界网络流+例题

序:

最近学了带上下界的网络流,现在就来讲一讲…

无源汇上下界可行流

  • 假设你已经会正常的网络流了…
  • 无源汇上下界可行流是什么呢?
  • 就是给你一个图,它没有源点汇点,然后让你给这个图加流,使之可以自己循环往复,形成一个有流的图.就像很多水管,你把他们头尾相连,在给一个流量,水就开始在管子里一圈圈的流了…
  • 无源汇上下界可行流就是找到一种可行的情况,这是所以上下界网络流的基础..
  • 现在给出这个图,每一条路都有下界,为了让它满足最下界,所以我们先让所有边流到下界,虽然这样可能导致一些点流量不平衡,即:一个点进入的流量与出来的流量不等…
  • 接下来我们引入一个新概念,就是附加流,该附加流不满足流量守恒,但是他与初始流附加以后将满足流量守恒。
  • 然后,我们怎么求附加流呢,对于所有边我们给他的流量变为上界和下界的差,然后对于那些流量不守恒的点我们设一个数组,A[i]表示流入这个点的流量减去流出这个点的流量.
  • 然后我们建立一个超级源SS(区分于S)和一个超级汇…
  • 对于A[i]>0,表面流入的太多了,那么我们从超级源连一条流量A[i]的边到当前点,这样,就可以让流出的流量加上A[i]从而流量守恒…毕竟我们不可以减少流入的量,只能增加流出的量…
  • 对于A[i]<0,同理,我们建一条流量是-A[i]的边到超级汇…
  • 然后从超级源到超级汇跑最大流,当超级源流出的边都跑满时,说明存在可行流…

有源汇上下界可行流

  • 对于这种情况我们要对图进行转换,我们也先让所有边跑到下界,同样这样导致流量不守恒,然后我们找到一个办法把有源汇变成无源汇.就是从T向S连一条流量不要求的边,这样就变成无源汇的了.
  • 然后根据流量守恒定律,在用无源汇上下界可行流跑出可行流以后,从T到S的流量就是可行流的流量…

例题: BZOJ2406/luoguP4194 矩阵

题意:

  • 给出一个矩阵A,让你再找一个矩阵B,B中的所有元素都处在[L,R],然后问你:A,B同一行或列差的绝对值的最大值的最小值。。。

分析:

  • 因为数据范围不大,然后大概是先二分一个最大值,然后所有行或列都满足: \vert S_{Ai}-S_{Bi} \vert \le M
  • 然后我们展开来看,就是S_{Ai}-M \le S_{Bi} \le S_{Ai}+M.
  • 那么我们就可以建出图来…
  • 我们找一个源点向所有行连[max(0,S_{Ai}-mid),S_{Ai}+mid]的边
  • 同理,所有列向汇点连[max(0,S_{Bi}-mid),S_{Bi}+mid]的边
  • 然后,枚举每一个点,把点所在的行和列用[L,R]连起来…
  • 建好图以后就用上文说到方法,求有源汇上下界网络流就好了…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e6+10;
const LL mod=1e9+7;
const LL inf=998244353;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,l,r,L,R,ans=-1,s,t,ss,tt;
int x[210][210],sa[2100],sb[2100],cur[8000];
struct Edge{int next,to,flow;}edge[N];
int head[10000],cnt,cha[800],dep[800];
queue<int> q;
void add(int from,int to,int flow){edge[++cnt]={head[from],to,flow};head[from]=cnt;}
void insert(int from,int to,int flow){add(from,to,flow);add(to,from,0);}
bool BFS()
{
    memset(dep,-1,sizeof(dep));
    q.push(ss);dep[ss]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int to=edge[i].to;
            if(edge[i].flow==0) continue;
            if(dep[to]==-1) dep[to]=dep[now]+1,q.push(to);
        }
    }
    return dep[tt]!=-1;
}
int DFS(int now,int flow)
{
    if(now==tt||!flow) return flow;
    int used=0;
    for(int &i=cur[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(dep[to]==dep[now]+1&&edge[i].flow&&flow-used>0)
        {
            int flag=DFS(to,min(flow-used,edge[i].flow));
            if(flag>0)
            {
                edge[i].flow-=flag;
                edge[i^1].flow+=flag;
                used+=flag;
            }
        }
        if(flow-used==0) break;;
    }
    return used;
}
int dinic(int ret=0)
{
    while(BFS()) 
    {
        memcpy(cur,head,sizeof(int)*(n+m+10));
        ret+=DFS(ss,inf);
    }
    return ret;
}
bool solve(int now)
{
    cnt=1;int sum=0;
    memset(cha,0,sizeof(cha));
    memset(head,0,sizeof(head));
    for(int i=1;i<=n;i++)
    {
        int ll=max(0,sa[i]-now),rr=sa[i]+now;
        insert(s,i,rr-ll);cha[s]-=ll;cha[i]+=ll;
    }
    for(int i=1;i<=m;i++)
    {
        int ll=max(0,sb[i]-now),rr=sb[i]+now;
        insert(i+n,t,rr-ll);cha[i+n]-=ll;cha[t]+=ll;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            insert(i,j+n,R-L),cha[i]-=L,cha[j+n]+=L;
    for(int i=0;i<=n+m+1;i++)
        if(cha[i]<0) insert(i,tt,-cha[i]);
        else insert(ss,i,cha[i]),sum+=cha[i];
    insert(t,s,inf);
    return sum==dinic();
}
signed main()
{
    // freopen("in","r",stdin);
    read(n),read(m);
    s=0,t=n+m+1;
    ss=n+m+2;tt=n+m+3;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            read(x[i][j]),sa[i]+=x[i][j],sb[j]+=x[i][j];
    read(L),read(R);
    l=0,r=210000;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(solve(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

有源汇上下界最大流

  • 我们先找到一个可行流,这个时候超级源已经流满了,然后它失去了作用,我们可以删掉它以及T向S连的那条无限边…
  • 接下来,跑一边从S到T跑最大流,最后答案就是可行流,加最大流…

有源汇上下界最小流

  • 同样我们先找一个可行流,然后想我们可不可以向最大流一样跑出最小流,但是没有这种操作…
  • 然后我们想我们跑出可行流以后的残余网络里有许多反向边,当我们走过这条边的时候就是在反悔,那么我们从T到S跑一遍最大流,然后用可行流减掉就好了…

例题:luoguP4843 清理雪道

题面:

  • 滑雪场坐落在FJ省西北部的若干座山上。
  • 从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。
  • 你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。
  • 由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。

分析:

  • 对于上面这个模型我们怎么建图呢…
  • 我们对于所有位置都从源点拉一条[0,inf]的边,然后拉一条[0,inf]的到T;
  • 对于相连的滑雪场,已知每一条路径都要被清扫到,那么我们就对连着的点加一条[1,inf]的边…
  • 接下来按照上文的套路跑就好了…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e6+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());   
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,l,r,L,R,ans=-1,s,t,ss,tt;
int x[210][210],sa[2100],sb[2100],cur[8000];
struct Edge{int next,to,flow;}edge[N];
int head[10000],cnt,cha[800],dep[800];
queue<int> q;
void add(int from,int to,int flow){edge[++cnt]={head[from],to,flow};head[from]=cnt;}
void insert(int from,int to,int flow){add(from,to,flow);add(to,from,0);}
bool BFS(int _S,int _T)
{
    memset(dep,-1,sizeof(dep));
    q.push(_S);dep[_S]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int to=edge[i].to;
            if(edge[i].flow==0) continue;
            if(dep[to]==-1) dep[to]=dep[now]+1,q.push(to);
        }
    }
    return dep[_T]!=-1;
}
int DFS(int now,int _T,int flow)
{
    if(now==_T||!flow) return flow;
    int used=0;
    for(int &i=cur[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(dep[to]==dep[now]+1&&edge[i].flow>0)
        {
            int flag=DFS(to,_T,min(flow-used,edge[i].flow));
            if(flag>0)
            {
                edge[i].flow-=flag;
                edge[i^1].flow+=flag;
                used+=flag;
            }
        }
        if(flow-used==0) break;
    }
    return used;
}
int dinic(int _S,int _T,int ret=0)
{
    while(BFS(_S,_T)) 
    {
        memcpy(cur,head,sizeof(int)*(n+m+10));
        ret+=DFS(_S,_T,inf);
    }
    return ret;
}
void del(int now){edge[now].flow=edge[now^1].flow=0;}
signed main()
{
    read(n);cnt=1;
    s=0,t=n+1,ss=n+2,tt=n+3;
    for(int i=1,u,v;i<=n;i++)
    {
        read(u);insert(s,i,inf),insert(i,t,inf);
        for(int j=1;j<=u;j++)
            read(v),insert(i,v,inf),cha[i]--,cha[v]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(cha[i]>0) insert(ss,i,cha[i]);
        else insert(i,tt,-cha[i]);
    }
    insert(t,s,inf);
    dinic(ss,tt);
    ans=edge[cnt].flow;
    del(cnt);
    for(int i=head[ss];i;i=edge[i].next) del(i);
    for(int i=head[tt];i;i=edge[i].next) del(i);
    ans-=dinic(t,s);
    printf("%d\n",ans);
    return 0;
}   

关于“上下界网络流+例题”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注