有上下界网络流

【写在前面】：
    为什么要来写这个东西呢？
    记得第一次解除是在初三的时候，具体动机我已经忘了
    但是那是太弱了，没有看懂，只是强行记住了一些结论
    这次的NOI2015 Day2 T3告诉我这是个很有用的东西
    我们不是Po姐，所以如果不会最小流T3就是死路一条...
【参考】：

【分类】：
    首先这种问题大致可以分为3类：
    无源汇有上下界最大流
    有源汇有上下界最大流
    有源汇有上下界最小流
    （为啥没有“无源汇有上下界最小流”呢？
【问题】：
    尽管三类问题有些不同，但相同点就是“有上下界”
    何谓“有上下界”呢？
    顾名思义：给出A(u,v)<=B(u,v)（(u,v)属于网络图）
    那么对于任意一条边(u,v)，他的流量满足A(u,v)<=f(u,v)<=B(u,v)
    即每条边最少流过A(u,v)，最多流过B(u,v)
【基础】：
    对于网络流来说有一条性质最为基础，即流量平衡
    既满足：sigma(f(u,i))=sigma(f(i,v))
【一些约定】：
    为了方便说话，我们做一些约定：
    设网络图为G=(V,E)
    设E中的每条起点为u终点为v下界为down上界为up的边为(u,v,down,up)
【无源汇有上下界最大流】：
    首先我们这样想：既然要满足所有下界被满足，那么我们可以直接流过下界
    也就是说我们可以把边(u,v,down,up)直接改为(u,v,0,up-down)
    这样题目就转化为没有下界的网络流了
    但是注意【基础】中所提及的流量守恒，这样跑出来的结果不一定满足流量守恒
    那么我们怎么判断是否存在一种方案满足流量守恒呢？
    我们从简单入手：假设有两条边(u,i,down1,up1)和(i,v,down2,up2)
    我们第一条边初始流过down1，第二条边初始流过down2
    我们发现如果down1=down2那么一切平安无事
    如果down1>down2那么说明我们的第二条边还要流过down1-down2
    如果down1<down2那么说明我们的第一条边还要流过down2-down1
    那么怎么使得这些边满足呢？
    我们设置源点s，汇点t
    如果down1>down2，那么连边(s,i,0,down1-down2)
    如果down1<down2，那么连边(i,s,0,down2-down1)
    然后如果跑最大流发现与s相连和与t相连的边都都流满了那么说明一下两个事实：
    “如果down1>down2那么说明我们的第二条边能够流过down1-down2”
    “如果down1<down2那么说明我们的第一条边能够流过down2-down1”
    那么原图存在满足的流，这样就可以判断可行性了
    由于没有实际的源汇，所以求没有必要求出最大流
【有源汇有上下界最大流】：
    顾名思义就是有源点s和汇点t
    首先我们可以判定是否存在可行流
    我们添加边(t,s,0,INF)就可以把图转化为无源汇的网络图了
    然后添加S，T，用上面的方法即可判定
    然后现在求得的maxflow并不是答案
    因为此时只是满足了所有下界，原图中s t的一些路径上还有残余的流量没有跑完
    所以我们就要把S，T以及相连的正向边删去，然后求s到t的maxflow，两次的maxflow之和即为答案
    注意第二次求最大流时虽然删除了S，T但是与之相连的反向弧并没有消失，所以实际上点集V还是包含了S，T的（注意初始点集大小
【有源汇有上下界最小流】：
    这个似乎是最难的，我们考虑依旧有上述方法
    然而我们发现了反例，如下图：(http://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html)

    原图存在循环流我们没有利用，导致最小流变大
    我们考虑这样做：先不添加(t,s,0,INF)，直接跑一边Sap(S,T)，然后加上(t,s,0,INF)，在跑一遍Sap(S,T)
    第二次的Sap如果满流那么就存在可行解，并且(t,s)的反向弧的流量就是答案
    因为此时正向弧流量最大，那么反向弧就最小啦...
【有源汇有上下界费用流】：
    方法如出一辙（注意此时边的四元组变成五元组，即多了一个费用）
    我们依旧连边(t,s,0,INF,0)
    然后建立S T，依旧按照入度出度连边即可
    然后跑EK(S,T)即可
    UPD：注意这样跑是不对的，我们还要把S T还有(t,s,0,INF,0)删去，然后再跑EK(s,t)才对，理由同上！

例题什么的以后再补

zoj 3231

【题目大意】：
    给你一棵Iphone 苹果 ios 树，然后每个结点上有一定的Iphone 苹果 ios 树，你要将Iphone 苹果 ios 运输达到某个状态，使得均方差最小。 将Iphone 苹果 ios x个从a->b的花费是x*w，w是边权。
【题目解法】：
    上下界费用流
    显然每个数都应该尽量往平均数靠拢，但是如果平均数不是整数，就要考虑某些点可能会多一个
    设平均数为ave
    连边(s,i,0,a[i],0)
    连边(i,j,0,INF,w)
    连边(i,t,ave,ave+1,0)
    用上面的方法即可，注意要跑两边EK

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=110;
const int M=10005;
const int size=800005;
const int INF=320832088;
struct edge {int x,y,c,f,op,next;} b[M]; bool v[N];
int n,tot,a[N],dis[N],cur[N],pre[N],q[M],ans,s,t,S,T,ave;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10LL+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void addedge(int x,int y,int c,int f)
{
    ++tot; b[tot].x=y; b[tot].c=c; b[tot].f=f; b[tot].op=tot+1; b[tot].next=a[x]; a[x]=tot;
    ++tot; b[tot].x=x; b[tot].c=0; b[tot].f=-f; b[tot].op=tot-1; b[tot].next=a[y]; a[y]=tot;
}
void init()
{
    tot=0; memset(a,0,sizeof(a)); ans=0;
    s=0; t=n+1; S=t+1; T=S+1; ave=0;
    for (int i=1; i<=n; i++)
    {
        int x=getint(); ave+=x;
        addedge(s,i,x,0);
    }
    for (int i=1; i<n; i++)
    {
        int x=getint()+1,y=getint()+1,z=getint();
        addedge(x,y,INF,z); addedge(y,x,INF,z);
    }
    ave=ave/n;
    for (int i=1; i<=n; i++) addedge(i,t,1,0);
    for (int i=1; i<=n; i++) addedge(i,T,ave,0);
    addedge(S,t,ave*n,0); addedge(t,s,INF,0);
}
bool spfa()
{
    memset(pre,0,sizeof(pre)); memset(cur,0,sizeof(cur));
    memset(dis,127,sizeof(dis)); int inf=dis[0];
    memset(v,true,sizeof(v)); dis[S]=0; v[S]=false;
    int head=0,tail=1; q[tail]=S;
    while (head<tail)
    {
        ++head; if (head>=size) head=1; int k=q[head]; v[k]=true;
        for (int p=a[k];p;p=b[p].next)
        {
            int pp=b[p].x;
            if ((b[p].c<=0)||(dis[k]+b[p].f>=dis[pp])) continue;
            dis[pp]=dis[k]+b[p].f; pre[pp]=k; cur[pp]=p;
            if (v[pp]) {++tail; if (tail>=size) tail=1; q[tail]=pp; v[pp]=false;}
        }
    }
    return dis[T]<inf;
}
void augment()
{
    int flow=INF;
    for (int i=T; i!=S; i=pre[i]) flow=min(flow,b[cur[i]].c);
    for (int i=T; i!=S; i=pre[i]) b[cur[i]].c-=flow,b[b[cur[i]].op].c+=flow;
    ans+=flow*dis[T];
}
void solve()
{
    while (spfa()) augment();
    a[S]=a[T]=0; a[s]=b[a[s]].next; a[t]=b[a[t]].next; S=s; T=t;
    while (spfa()) augment();
    printf("%d\n",ans);
}
int main()
{
    //freopen("1.in","r",stdin);
    while (scanf("%d",&n)!=EOF)
    {
        init();
        solve();
    }
    return 0;
}

zhouzixuan的博客

博客

未完待续

评论

发表评论