【题解】XWW 的难题 有源汇的上下界网络流 BZOJ – 3698

https://www.mina.moe/BZPRO/JudgeOnline/3698.html

这题目好难啊 QAQ

设 $l[i][j]$表示 $a[i][j]$向下取整，$r[i][j]$表示 $a[i][j]$向上取整

就如下连边：

• $S->X[i]$：下界为 $l[i][n]$，上界为 $r[i][n]$
• $X[i]->Y[j]$：下界为 $l[i][j]$，上界为 $r[i][j]$
• $Y[j]->T$：下界为 $l[n][j]$，上界为 $r[n][j]$

其中 $i, j \leq n – 1$

这样等于限制了每一行、列前 $n – 1$个元素的和，用 $X[i]->Y[j]$的流量表示了 $a[i][j]$的取值

接下来就是一个有源汇的上下界网络流，化为无源汇的可行流再跑出最大流就行啦。

太妙了哈哈哈^_^

#include <bits/stdc++.h>

#define NS (10005)
#define MS (3000000)

using namespace std;

struct Graph
{
    int head[NS], nxt[MS], to[MS], f[MS], sz;
    void init() {memset(head, -1, sizeof(head)), sz = 0;}
    Graph() {init();}
    void push(int a, int b, int c)
    {
        nxt[sz] = head[a], to[sz] = b, f[sz] = c, head[a] = sz++;
        nxt[sz] = head[b], to[sz] = a, f[sz] = 0, head[b] = sz++;
    }
    int operator [] (const int a) const {return to[a];}
} g;

int n, S, T, dt[NS];

int dep[NS], cur[NS];

queue<int> que;

bool Bfs(int s, int t)
{
    while (!que.empty()) que.pop();
    memset(dep, 0, sizeof(dep)), dep[s] = 1, que.push(s);
    while (!que.empty())
    {
        int F = que.front(); que.pop();
        for (int i = g.head[F]; ~i; i = g.nxt[i])
            if (!dep[g[i]] && g.f[i])
                dep[g[i]] = dep[F] + 1, que.push(g[i]);
        if (dep[t]) return 1;
    }
    return 0;
}

int Dfs(int a, int t, int f)
{
    if (a == t) return f;
    for (int& i = cur[a]; ~i; i = g.nxt[i])
        if (g.f[i] && dep[a] + 1 == dep[g[i]])
        {
            int tmp = Dfs(g[i], t, min(f, g.f[i]));
            if (tmp) {g.f[i] -= tmp, g.f[i ^ 1] += tmp; return tmp;}
        }
    return 0;
}

bool Jud()
{
    int tot = 0, SS = T + 1, TT = T + 2;
    for (int i = 0; i <= T; i += 1)
    {
        if (dt[i] > 0) g.push(SS, i, dt[i]), tot += dt[i];
        else if (dt[i] < 0) g.push(i, TT, -dt[i]);
    }
    g.push(T, S, 1e8);
    while (Bfs(SS, TT))
    {
        memmove(cur, g.head, sizeof(cur));
        int tmp;
        while (tmp = Dfs(SS, TT, 1e8)) tot -= tmp;
    }
    return (tot == 0);
}

int main(int argc, char const* argv[])
{
    scanf("%d", &n), n--, S = 0, T = (n << 1) + 1;
    for (int i = 1; i <= n + 1; i += 1)
        for (int j = 1, l, r; j <= n + 1; j += 1)
        {
            double x; scanf("%lf", &x);
            if (i == n + 1 && j == n + 1) break;
            l = floor(x), r = ceil(x);
            if (j == n + 1) dt[S] -= l, dt[i] += l, g.push(S, i, r - l);
            else if (i == n + 1)
                dt[j + n] -= l, dt[T] += l, g.push(j + n, T, r - l);
            else dt[i] -= l, dt[j + n] += l, g.push(i, j + n, r - l);
        }
    if (!Jud()) {puts("No"); return 0;}
    int ans = 0;
    while (Bfs(S, T))
    {
        memmove(cur, g.head, sizeof(cur));
        int tmp;
        while (tmp = Dfs(S, T, 1e8)) ans += tmp;
    }
    printf("%d\n", ans * 3);
    return 0;
}