题解 P5192 【Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流】

whiteqwq · 2020-04-19 22:34:04 · 题解

Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流解题报告

标签：解题报告

Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流解题报告：

可能更好的阅读体验

~~先吐槽一下，这虽然是板子题，但看懂怎么建模还要一小会儿~~

~~还有，为什么要把三倍经验合并啊~~

题意与分析

题意：一共有n天，每天最多拍D_i张照骗照片，有C_i个取材对象，每个取材对象T_{i,j}需要拍[L_{i,j},R_{i,j}]的照片，同时m个少女中每个少女的照骗数量不得少于G_i。

我们很容易从~~标题：【模板】有源汇上下界最大流~~“[L_{i,j},R_{i,j}]”和“不得少于G_i”看出来需要求有源汇上下界最大流

无源汇上下界可行流

我们考虑一个问题：在一张图中，每条边有流量下界和流量上界，求是否存在一种方案在满足流量平衡的情况下，使所有边满足上下界限制。

注意：这里的流量平衡指：对于所有点x，满足\forall_{e\in E,e.to==x}e.flow=\forall_{e'\in E,e'.from==x}e'.flow（e.from与e.to分别为一条边的两个点，e.flow为这条边实际的流量），即对于每个点都满足流入它的流量等于流出它的流量。

很容易想到一种想法，我们把上限减去下限，然后跑最大流。但是这个很显然是不满足的，因为经过操作后可能会形成这样的图：，这张图是很显然没有可行流的。但是经过操作后，原图会变为：，此时存在可行流。

我们发现答案前后不一的原因是经过这种操作后新图不满足流量平衡了，这就很麻烦了，跑不了最大流，~~而且也不能随便发明一个不需要流量平衡的最大流算法~~，因此我们想想如何经过玄学操作是新图满足流量平衡。

对了！原点和汇点还在旁边晾着，我们要让它们干活。因为最大流算法中源点和汇点可以不满足流量平衡，因此我们可以把锅推到源点和汇点上，同样是把每条边上限减去下限，但是对于每个点，我们计算in_x=\forall_{e\in E,e.to==x}e.flow，out_x=\forall_{e\in E,e.from==x}e.flow，为了满足流量平衡，x可以获得的流量肯定是min(in_x,out_x)，此时不满足流量平衡的地方就是\left|in_x-out_x\right|了。因此，对于所有的in_x>out_x，我们从s向x连一条上限为in_x-out_x的边来补齐由于流量平衡损失的流量；对于所有的in_x==out_x，可以连边可以不连边；对于所有的in_x<out_x，我们从x向t连一条上限为out_x-in_x的边补齐由于流量平衡损失的流量。

简单来说，所有连向x的边抬高了x一共in_x的下限，所有从x连出的边抬高了x一共out_x的下限。为了让x连入和连出处于同一个水平，我们需要用可以不满足流量平衡的s和t抬高或降低x的下限（等于从连入经过一次抬高/降低再连出），这样可以让x处于流量平衡的状态。

因此，这个步骤已经很明了了：

统计每个点x的in_x与out_x，即连向x的边的流量之和与连出x的边的流量之和。
对于每一条原图里的边，流量设为上限减去下限，因此得到一张新图。
虚拟源点与汇点s和t，对于所有的x，如果in_x>out_x，则从s向x连一条in_x-out_x的边，否则从x向t连一条out_x-in_x的边。
跑一遍从s到t的最大流，如果s连出的边可以满流（由于流量平衡，等价于连向t的边可以满流），证明存在可行流。

有源汇上下界可行流

考虑有源点和汇点的上下界可行流，即在无源汇上下界可行流的基础上增加两个点不满足流量守恒。

由于流量平衡流出s的流量很显然与流入t的流量是相等的，那么我们很容易发现只要连接一条(t,s,inf)的边，原图就可以转化为无源汇上下界可行流的裸题了！

因此，步骤为：

从原图中的汇点向源点连一条上限为inf的边。
跑一遍无源汇上下界可行流。

有源汇上下界最大流

接下来，我们看有源汇的上下界最大流。我们并不满足于求可行流，在找可行流的基础上，还想找最大流，这样应该怎么办呢？

我们先找到一个可行流flow1，此时我们“榨干”了连接虚拟源点和虚拟汇点的边，因此我们不能再跑一遍从虚拟源点到虚拟汇点的最大流，因为这根本没有意义。

但是这个可行流不一定是最大流，因为可行流只会跑满与虚拟源点和虚拟汇点相连的边，因此flow1最多就是这些边的上限和，此时在原图中可能会有边是跑不满的。

因此我们考虑计算flow2为flow1还能向上浮动的流量（这里需要感性理解），那么如何求flow2呢？其实向上浮动某些流量可以等价于在原图中跑出增广路（很显然，因为每跑出一个增广路就会让答案+1），因此我们跑一遍从原图中的源点到原图中的汇点的最大流，并设其答案为flow2。

此时ans=flow1+flow2。

注意一点，在跑原图的最大流时需要删去从原图汇点到原图源点的边，如果这条边没有删去，则会导致死循环。

但是与虚拟源点和虚拟汇点相连的边可以不删去，因为在求第一次最大流的时候就已经将这些边“榨干”了（因为是满流），否则根本不存在可行流。

步骤：

跑出一个有源汇上下界可行流，如果满流则设其答案为flow1，否则不存在答案。
删去从原图汇点到原图源点的边。
跑从原图源点到原图汇点的最大流，设答案为flow2，则总答案ans=flow1+flow2。

回归题目

让我们回归题目，~~很容易~~可以看出来题目的建模方式：先虚拟一个源点s和一个汇点t，然后每天和每位少女分别建一个点，P_i与Q_i。首先连接所有的Q_i和t，下限为G_i，上限为inf。然后，连接s和所有的P_i，下限为0，上限为D_i。对于第i天，取材对象为T_{i,j}，取材数量为[L_{i,j},R_{i,j}]时，连接D_i和T_{i,j}，下限为L，上限为T。这样，就完成了原图的建模。

然后就按照有源汇上下界最大流的建模继续就ok了。

代码

注意：少女的编号是从0开始的，而且有多组数据，记得清零数组与变量

#include<stdio.h>
#include<queue>
#include<string.h>
#define inf 2147483647
using namespace std;
const int maxn=1000005,maxm=1000005;
int i,j,k,m,n,s,t,s1,t1,s2,t2,e,flg,ans,sum,anss;
int start[maxn],to[maxm],then[maxm],worth[maxm],rev[maxm],dep[maxn],vis[maxn],in[maxn],out[maxn],G[maxn];
queue<int>q;
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y,int z,int r){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z,rev[e]=r;
}
inline void addedge(int x,int y,int z){
    add(x,y,z,e+2),add(y,x,0,e);
}
void bfs(){
    while(!q.empty())
        q.pop();
    for(int i=1;i<maxn;i++)
        dep[i]=inf,vis[i]=0;
    dep[s]=0;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=start[x];i;i=then[i]){
            int y=to[i];
            if(worth[i]&&dep[y]>dep[x]+1){
                dep[y]=dep[x]+1;
                if(vis[y]==0){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
int dfs(int x,int flw){
    if(x==t){
        flg=1,ans+=flw;
        return flw;
    }
    int rest=flw;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(worth[i]&&dep[y]==dep[x]+1){
            int newflw=dfs(y,min(rest,worth[i]));
            if(newflw>0){
                rest-=newflw;
                worth[i]-=newflw,worth[rev[i]]+=newflw;
                if(rest==0)
                    break;
            }
            else dep[y]=0;
        }
    }
    return flw-rest;
}
int Dinic(){
    ans=0;
    while(1){
        bfs();
        if(dep[t]==inf)
            break;
        flg=1;
        while(flg){
            flg=0;
            dfs(s,inf);
        }
    }
    return ans;
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        sum=e=0;
        memset(start,0,sizeof(start));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        s1=n+m+1,t1=n+m+2,s2=n+m+3,t2=n+m+4;
        s=s2,t=t2;
        for(i=1;i<=m;i++){
            scanf("%d",&G[i]);
            in[t1]+=G[i],out[n+i]+=G[i];
            addedge(n+i,t1,inf-G[i]);
        }
        for(i=1;i<=n;i++){
            int C,D,T,L,R;
            scanf("%d%d",&C,&D);
            addedge(s1,i,D);
            for(j=1;j<=C;j++){
                scanf("%d%d%d",&T,&L,&R);
                T++;
                in[n+T]+=L,out[i]+=L;
                addedge(i,n+T,R-L);
            }
        }
        for(i=1;i<=n+m+2;i++){
            if(in[i]>out[i])
                addedge(s,i,in[i]-out[i]),sum+=in[i]-out[i];
            else addedge(i,t,out[i]-in[i]);
        }
        addedge(t1,s1,inf);
        if(Dinic()!=sum){
            puts("-1\n");
            continue;
        }
        anss=worth[e];
        worth[e]=worth[rev[e]]=0;
        s=s1,t=t1;
        anss+=Dinic();
        printf("%d\n\n",anss);
    }
    return 0;
}

扩展-有源汇上下界最小流

我们看到有源点和汇点的上下界最小流，即在可行流的基础上要求流量最小。

我们先跑一遍可行流，设可行流为flow1

则最小流为可行流-还能向下浮动的流量flow2

其实我们可以发现还能向下浮动的流量就是从原图汇点到原图源点的最大流（感性理解）。

因此步骤为：

跑出一个有源汇上下界可行流，如果满流则设其答案为flow1，否则不存在答案。
删去从原图汇点到原图源点的边。
跑从原图汇点到原图源点的最大流，设答案为flow2，则总答案ans=flow1-flow2。