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

• $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]$

#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;
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++;
}
} 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))
{
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))
{
int tmp;
while (tmp = Dfs(S, T, 1e8)) ans += tmp;
}
printf("%d\n", ans * 3);
return 0;
}


Remmina

No puzzle that couldn't be solved.