Blabla

最近刷了下网络流的题目,是该写篇小结了。

后面会有网络流的题目,供大家参考。

网络流简介

这部分相对简单,网上资料也很多,就当大家都会吧(不会的自行google)

网络流的分类以及实现

  • 最大流: sap或dinic。如果是平面图,则还可以用最短路做。
  • 费用流: spfa或zkw费用流
  • 最小割: 先求最大流,然后bfs求方案。与最大流相同,如果是平面图,也可以直接最短路,则所经过的边就是割边。
  • 上下界网络流: 先把下界边都满流,上界 -= 下界,然后通过新建源汇,来实现分配流量,使得每个点都满足流量平衡。

本人蒟蒻,最大流只会sap。

费用流一般都用spfa实现。因为zkw不一定都比spfa快,也不好实现。

下面贴一下网上流传的代码(不知为何人所创),也是我在用的模板。sap部分至于为什么本蒟蒻也不太懂。反正:

神一般的实现,会背即可!

sap

复杂度为

int src,sink,dis[N],cnt[N],Vc,ec,n;
struct Edge{int link,next,f;}es[M];
inline void addedge(const int x,const int y,const int z)
{
    es[ec].link = y;
    es[ec].next = son[x];
    es[ec].f = z;
    son[x] = ec++;
}
inline void Addedge(const int x,const int y,const int z){addedge(x,y,z);addedge(y,x,0);}
int sap(const int u,const int aug)
{
    if (u == sink) return aug;
    int sum = 0,Min = Vc;
    for (int i = son[u]; ~i; i = es[i].next) {
        const int v = es[i].link;
        if (es[i].f && dis[v] + 1 == dis[u]) {
            int t = sap(v,std::min(aug - sum,es[i].f));
            es[i].f -= t; es[i ^ 1].f += t; sum += t;
            if (sum == aug || dis[src] >= Vc) return sum;
        }
        if (es[i].f && Min > dis[v]) Min = dis[v];
    }
    if (!sum) {
        if (!--cnt[dis[u]]) dis[src] = Vc;
        ++cnt[dis[u] = Min + 1];
    }
    return sum;
}
int main()
{
    memset(dis,0,sizeof dis);
    src = 0; sink = n + 1;
    cnt[0] = Vc = sink + 1;
    while (dis[src] < Vc) ans += sap(src,INF);
}

spfa费用流

//以下是最小费用流。用邻接矩阵存储的。
bool SPFA()
{
    static bool inq[N];
    static std::queue<int> q;
    memset(dis,0x3f,sizeof dis);
    inq[src] = 1; dis[src] = 0;
    for (q.push(src); !q.empty(); q.pop()) {
        const int u = q.front();
        inq[u] = 0;
        for (int i = son[u]; i; i = es[i].next) {
            const int v = es[i].link;
            if (cap[u][v] && dis[v] > dis[u] + cost[u][v]) {
                pre[v] = u;
                dis[v] = dis[u] + cost[u][v];
                if (!inq[v]) inq[v] = 1, q.push(v);
            }
        }
    }
    return dis[sink] != 0x3f3f3f3f;
}
int Cost_Flow()
{
    int ans = 0;
    while (SPFA()) {
        int Min = 0x7ffffff;
        for (int i = sink; i != src; i = pre[i])
            Min = std::min(Min,cap[pre[i]][i]);
        for (int i = sink; i != src; i = pre[i])
            cap[pre[i]][i] -= Min,cap[i][pre[i]] += Min;
        ans += Min * dis[sink];
    }
    return ans;
}

网络流的应用

网络流重在构图,应用千变万化。由于本人水平有限,就只能讲一些比较常见的简单的做法。

拆点

顾名思义,就是把一个点拆成多个点。有时候是一个点作为入点,另一个作为出点,而连接这两个点的边往往大有玄机。有时候是每个点代表一个时间,将整张图分成若干层,方便处理。详见NOI美食节以及网络流24题。

点与边之间的转化

有许多题目给了你点,而最终构图其实是被转化成了流量,很赞的思想。可以参考poj2396

取或者不取

大家都知道,割的意义就是每条边选或者不选。而这给了它极大的拓展性。

例如给你n个点,每个点有权值,再给你一些两个点之间的约束,往往就可以转化成最小割。

对于这一方面个人力荐彭天翼神犇的论文,十分浅显易懂。

特殊的线性规划

简单的讲就是每个变量xi出现的不等式位置都是连续的,而且xi >= 0,不等式要同向。然后就可以将不等化等(在某一边+yi),作差。之后每个变量只出现了正负两次。然后对每个等式都建立流量平衡。对于-xi连向+xi,yi也一样。而其他的常数根据正负选择是连到源还是汇。

对偶

比较简单就是平面图实现最小割的转化。

而复杂一点的就是对偶原理:最大与最小的转化(其实最大流与最小割也是如此)。可以参考[Zjoi2013]防守战线。

这里推荐几个对对偶的论述: http://wenku.baidu.com/view/e9acc41dc5da50e2524d7ffb.html,http://www.cnblogs.com/zyearn/

题目

仅仅做了一点。可能有重复。

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project