Description
有n個變數w[1]~w[n]，每個變數可以取W或-W，
有p個式子，形如Hi=ai|w[xi]-w[yi]|+bi|w[yi]-w[zi]|+ci|w[zi]-w[xi]|+di(w[xi]-w[yi])+ei(w[yi]-w[zi])+fi(w[zi]-w[xi])，
有q個條件，形如w[x]<=w[y]或w[x]=w[y]或w[x]<w[y]，
最小化sigma(wi)+sigma(Hi)，
Data Constraint
資料組數≤10，n≤500, p,q≤1000, W≤10^6, 系數≤10^3，所有數字∈N，
Solution
奇怪的條件限制+不大的資料范圍=網路流，
第一次做最小割+二元關系的題目，
考慮建圖，首先對于每個變數w，連正權邊S(s,i)和負權邊S(i,t)，割啥選啥
然后是 H(i)，先考慮 x, y，取絕對值 = 異號2a 同號為0 ? 連一條權值為2a的無向邊(x, y)
后面的有點復雜，拆開式子后化為 (d - f) * w ? 有向邊(s, x) += (d - f) * w，無向邊(x, t) -= (d - f) * w
再考慮限制條件，
w[x] ≤ w[y] ? 有向邊(y, x) = inf，表示要不然割(s, y)，要不然割(x, t)和(y, t)
w[x] = w[y] ? 無向邊(x, y) = inf，表示要不然同時割(s, x)(s, y)，要不然同時割(x, t)(y, t)
w[x] > w[y] ? 有向邊(s, x) = (y, t) = inf
這樣子圖就建好啦！
但是有負權邊…………
所有(s, x), (x, t) += inf（一個極大值但別超過最大值，超過了會不會WA我也不造，注意這里指無向邊）
其他的邊都是inf邊或補正邊可以不加（為什么？）
最后答案減去 n * inf （共割了n條邊）
最大流然后沒啦！
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501
#define M 1000
#define ll long long
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define Mes(a, x) memset(a, x, sizeof a)
#define Min(x, y) (x < y ? x : y)
void read(ll &x) {
char ch = getchar(); x = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - 48, ch = getchar();
}
const ll inf = (1ll << 40), INF = (1ll << 50);
int dis[N + 1], gap[N + 1], pre[N + 1], be[N + 1];
ll his[N + 1], f[N + 1][N + 1];
ll n, m, W, p, q;
ll Sap() {
Mes(dis, 0), Mes(gap, 0), Mes(be, 0);
gap[0] = m + 1;
ll sum = 0, aug = INF;
for (int u = 0, flow; dis[u] < m; ) {
his[u] = aug, flow = 0;
fo(i, be[u], m) if (f[u][i] > 0 && dis[u] - 1 == dis[i]) {
pre[i] = u;
aug = Min(aug, f[u][i]);
be[u] = i;
u = i;
flow = 1;
if (u == m) {
sum += aug;
while (u) {
f[u][pre[u]] += aug, f[pre[u]][u] -= aug;
u = pre[u];
}
aug = inf;
}
break;
}
if (flow) continue;
int v = 0;
fo(i, 0, m) if (f[u][i] > 0 && dis[i] < dis[v])
v = i;
if (-- gap[dis[u]] == 0) break;
++ gap[ dis[u] = dis[v] + 1 ];
be[u] = v;
if (u) u = pre[u], aug = his[u];
}
return sum;
}
int main() {
freopen("variable1.in", "r", stdin);
freopen("variable.out", "w", stdout);
ll T; read(T);
while (T --) {
Mes(f, 0);
read(n), read(W), read(p), read(q);
m = n + 1;
ll x, y, z, a, b, c, d, e, f1;
fo(i, 1, p) {
read(x), read(y), read(z), read(a), read(b), read(c), read(d), read(e), read(f1);
f[x][y] += (a << 1) * W, f[y][x] += (a << 1) * W;
f[y][z] += (b << 1) * W, f[z][y] += (b << 1) * W;
f[z][x] += (c << 1) * W, f[x][z] += (c << 1) * W;
f[0][x] += (d - f1) * W, f[x][m] -= (d - f1) * W;
f[0][y] += (e - d) * W, f[y][m] -= (e - d) * W;
f[0][z] += (f1 - e) * W, f[z][m] -= (f1 - e) * W;
}
fo(i, 1, n) f[0][i] += W, f[i][m] -= W;
fo(i, 1, n) f[0][i] += inf, f[i][0] += inf, f[i][m] += inf, f[m][i] += inf;
fo(i, 1, q) {
read(x), read(y), read(z);
if (z == 0) f[y][x] = INF;
else if (z == 1) f[x][y] = f[y][x] = INF;
else f[0][x] = f[y][m] = INF;
}
ll ans = Sap();
ans -= 1ll * n * inf;
printf("%lld\n", ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/19518.html
標籤：其他
上一篇：從尾到頭列印鏈表