先导知识

题目链接

https://vjudge.net/problem/ZOJ-3229

https://www.luogu.com.cn/problem/P5192 （有改动）

题目大意

多组数据，读到文件结束。

对于每一组数据，第一行为正整数\(n,m\)表示\(n\)天，\(m\)个少女。

接下来一行，\(m\)个正整数\(G_1,G_2 ... G_m\)分别表示每个少女总共至少要拍的照片张数。

接下来\(n\)组，每一组第一行有两个整数\(C_i,D_i\)，表示这一天有\(C_i\)个少女要拍照，这一天的照片总数不超过\(D_i\)。

接着有\(C_i\)行，每行三个整数\(k,L_k,R_k\)，表示在这一天里\(k\)号少女要拍的照片数目处于\([L_k,R_k]\)区间。

（注意少女是从\(0\)开始编号的。）

满足这些条件以后，所有天的照片总数越多越好。

如果有解输出照片总数，并按顺序输出每一天的少女拍照数目，否则输出\(-1\)，每组答案后输出一空行。

题目解析

这道题比较抽象，不是经典的模板，还需要经过一些变换，才可以变成裸的模板题。

题目为有源汇有上下界的最大流模板。

首先，对\(n\)天，每一天照片数存量\(\leq D_i\)；\(m\)个少女，每个少女照片数消耗\(\geq G_k\)。

若将每一天、每个少女看作点，则有上下限点权要求。

其次，每一天中，少女消耗照片数有\([L,R]\)限制，可看成从“天”的点集到“少女”点集的一条有向边。

那么，初步建立了一张二分图，分为“天”、“少女”两部分点集\(A,B\)，有向边方向一定是\(A \rightarrow B\)。

为了便于直观理解，这里选用了例题中的第一组 Sample Input 的数据进行绘图讲解。

将两个点集中“点权”的上下限看作从虚拟源点 \(s\) 流出或流入虚拟汇点 \(t\) 的“边权”上下限要求，就可以建好了一张“有源汇”的图，结合题目要求，我们知道当前任务转化为了这张图上的 有源汇有上下界最大流 。

接下来，怎样转化为我们熟悉的问题呢？

在“无源汇有上下界可行流”中，每一个结点都满足 流量平衡 。

但是在“有源汇”的图中，源点 \(s\) 及汇点 \(t\) 是不满足流量平衡的，这时，我们可以考虑连接一条从汇点 \(t\) 到源点 \(s\) 的，容量为 \(\infty\) 的有向边。

这样，既满足了源点 \(s\) 流出和汇点 \(t\) 流入无限的性质，又能使整张网络图上的点全都满足流量平衡，即转化成为了“无源汇”的问题。

根据解决“无源汇有上下界可行流”的方法，（用下界流填满各点，盈余为正者与新设虚拟源点 \(s'\) 相连，盈余为负者与新设虚拟汇点 \(t'\) 相连），可以查看上一篇博客解决的无源汇有上下界可行流问题进行回顾。

可以得到新图的“可行流”，再去除虚设的源汇，再跑一次最大流，即可得到本题的答案了，即，有源汇有上下界最大流。

各位读者可以根据样例，自行建图加深理解。

网络流的题目，一般只需要套用模板，而思维难点，往往在于将抽象问题转化为建有向图解决，需要多加练习。

后面博客会陆续更新，经典例题 网络流 \(24\) 题 的部分解题策略，欢迎浏览支持，多多指教！

参考代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1405;

const int INF = 2147483647;

struct Edge{

    int from, to, cap, flow, min;

};

int n, m, s, t, gap[N], cur[N], dep[N], R[N], cnt;

vector <Edge> e;

vector <int> G[N];

void init()

{

    memset(gap, 0, sizeof gap);

    memset(cur, 0, sizeof cur);

    memset(dep, 0, sizeof dep);

    ++gap[dep[t] = 1];

    queue <int> Q;

    Q.push(t);

    while (!Q.empty()) {

        int x=Q.front(); Q.pop();

        for (int i = 0; i < G[x].size(); i++)

        {

            int v = e[G[x][i]].to;

            if (!dep[v])

            {

                ++gap[dep[v] = dep[x]+1];

                Q.push(v);

            }

        }

    }

}

int augment(int x, int a)

{

    if (x == t || !a) return a;

    int flow = 0;

    for (int &i=cur[x]; i < G[x].size(); i++)

    {

        Edge& b = e[G[x][i]];

        if (dep[x] == dep[b.to] + 1 && b.cap > b.flow) {

            int tmp = augment(b.to, min(a, b.cap - b.flow));

            flow += tmp;

            a -= tmp;

            b.flow += tmp;

            e[G[x][i]^1].flow -= tmp;

            if (!a) return flow;

        }

    }

    if (!(--gap[dep[x]])) dep[s] = cnt+1;

    ++gap[++dep[x]], cur[x] = 0;

    return flow;

}

ll maxFlow()

{

    init();

    ll ans = 0;

    while (dep[s] <= cnt) ans += augment(s, INF);

    return ans;

}

void Clear()

{

    e.clear();

    for (int i = 0; i <= cnt; ++i) G[i].clear();

    memset(R, 0, sizeof R);

    n = m = s = t = cnt = 0;

}

void addEdge(int u, int v, int l, int c, int i)

{

    e.push_back((Edge){u, v, c-l, 0, l});

    e.push_back((Edge){v, u, 0, 0, 0});

    G[u].push_back(i);

    G[v].push_back(i^1);

    R[u] -= l;

    R[v] += l;

}

int main()

{

    int T = 0;

    while (scanf("%d%d", &n, &m) == 2)

    {

        int s1, t1;

        s1 = n + m + 1, t1 = s1 + 1;

        s = s1 + 2, t = t1 + 2;

        for (int i = 0; i < m; ++i) {

            int a;

            scanf("%d", &a);

            addEdge(i+1, t1, a, INF, i << 1);

        }

        int j = m-1;

        for (int i = m+1; i <= m+n; ++i) {

            int a, c, l, k;

            scanf("%d%d", &k, &a);

            addEdge(s1, i, 0, a, (++j) << 1);

            while (k--)

            {

                scanf("%d%d%d", &a, &l, &c);

                addEdge(i, a+1, l, c, (++j) << 1);

            }

        }

        int k = j;

        for (int i = 1; i < s; ++i) {

            if (R[i] > 0) addEdge(s, i, 0, R[i], (++k) << 1);

            else if (R[i] < 0) addEdge(i, t, 0, -R[i], (++k) << 1);

        }

        addEdge(t1, s1, 0, INF, (++k) << 1);

        cnt = n+m+4;

        ll a = maxFlow();

//        printf("maxflow = %lld\n", a);

//        for (int i = 0; i <= j; ++i) {

//            printf("%d -> %d (%d/%d)\n", e[i << 1].from, e[i << 1].to, e[i << 1].flow, e[i << 1].cap);

//        } //这一部分查看可以看新图的流量情况

        int flag = 0;

        for (int i = 0; i < G[s].size(); ++i) {

            if (e[G[s][i]].cap > e[G[s][i]].flow) {flag = 1; break;}

        }

        if (flag) printf("-1\n");

        else {

            s = s1, t = t1;

            printf("%lld\n", maxFlow());

            for (int i = m+1; i <= j; ++i) {

                if (e[i << 1].from > m && e[i << 1].to <= m) printf("%d\n", e[i << 1].flow+e[i << 1].min);

            }

        }

        Clear();

        putchar('\n');

    }

    return 0;

}

感谢支持！

巴特西

【模板】有源汇有上下界最大流（网络流）/ZOJ3229

先导知识

题目链接

题目大意

题目解析

参考代码

最新文章

热门文章