题意：你有一个棋盘，某些格子是限制条件，形如"从这里开始下面所有连续空格的和为a"或"从这里开始向右的所有连续空格之和为b"一个格子可以同时拥有两个限制条件。
每个数都必须是正整数。
现在你可以把某些格子加/减1，并花费相应的代价。可以操作无数次。求把棋盘变得合法的最小代价。
解：没想出来，看了题解......
一开始想了数字和条件构成二分图，又想了行列连边，但是始终建不出图来。
行列连边。
因为既可以加又可以减不好搞，我们可以先全部转换成满足条件的最小值，然后往上加。
从最小值到初始值的时候，边权为负。之后边权为正。
不可修改的地方边权为INF。
然后跑一个最小费用可行流就是答案。
如何判断无解？
考虑每条边，如果有的边费用为INF但是有流量，就不合法。
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring> typedef long long LL;
const LL N = , M = , INF = 0x3f3f3f3f, J = ; struct Edge {
LL nex, v, c, len;
}edge[N << ]; LL top = ; LL e[N], d[N], vis[N], pre[N], flow[N];
std::queue<LL> Q;
LL fr[J][J], val[J][J], v2[J][J], cst[J][J], c2[J][J], m; inline void add(LL x, LL y, LL z, LL w) {
top++;
edge[top].v = y;
edge[top].c = z;
edge[top].len = w;
edge[top].nex = e[x];
e[x] = top; top++;
edge[top].v = x;
edge[top].c = ;
edge[top].len = -w;
edge[top].nex = e[y];
e[y] = top;
return;
} inline bool SPFA(LL s, LL t) {
memset(d, 0x3f, sizeof(d));
d[s] = ;
flow[s] = INF;
vis[s] = ;
Q.push(s);
while(!Q.empty()) {
LL x = Q.front();
Q.pop();
vis[x] = ;
for(LL i = e[x]; i; i = edge[i].nex) {
LL y = edge[i].v;
if(edge[i].c && d[y] > d[x] + edge[i].len) {
d[y] = d[x] + edge[i].len;
pre[y] = i;
flow[y] = std::min(flow[x], edge[i].c);
if(!vis[y]) {
vis[y] = ;
Q.push(y);
}
}
}
}
return d[t] < INF;
} inline void update(LL s, LL t) {
LL temp = flow[t];
while(t != s) {
LL i = pre[t];
edge[i].c -= temp;
edge[i ^ ].c += temp;
t = edge[i ^ ].v;
}
return;
} inline LL solve(LL s, LL t, LL &cost) {
LL ans = ;
cost = ;
while(SPFA(s, t)) {
if(d[t] > ) {
break;
}
ans += flow[t];
cost += flow[t] * d[t];
update(s, t);
}
return ans;
} inline LL id(LL x, LL y) {
return (x - ) * m + y;
} int main() {
LL n, use = ;
scanf("%lld%lld", &n, &m);
for(LL i = ; i <= n; i++) {
for(LL j = ; j <= m; j++) {
scanf("%lld", &fr[i][j]);
}
}
for(LL i = ; i <= n; i++) {
for(LL j = ; j <= m; j++) {
if(fr[i][j] == ) {
continue;
}
else if(fr[i][j] == ) {
scanf("%lld", &val[i][j]);
}
else if(fr[i][j] == ) {
scanf("%lld", &v2[i][j]);
}
else if(fr[i][j] == ) {
scanf("%lld%lld", &val[i][j], &v2[i][j]);
}
else {
scanf("%lld", &val[i][j]);
}
}
}
for(LL i = ; i <= n; i++) {
for(LL j = ; j <= n; j++) {
if(fr[i][j] == ) {
continue;
}
else if(fr[i][j] == ) {
scanf("%lld", &cst[i][j]);
}
else if(fr[i][j] == ) {
scanf("%lld", &c2[i][j]);
}
else if(fr[i][j] == ) {
scanf("%lld%lld", &cst[i][j], &c2[i][j]);
}
else {
scanf("%lld", &cst[i][j]);
}
if(cst[i][j] == -) {
cst[i][j] = INF;
}
if(c2[i][j] == -) {
c2[i][j] = INF;
}
}
}
// read over
LL lm = n * m;
LL s = lm * + ;
LL t = s + ;
for(LL i = ; i <= n; i++) {
for(LL j = ; j <= m; j++) {
if(fr[i][j] == ) {
continue;
}
if(fr[i][j] == || fr[i][j] == ) {
// id(i, j)
LL cnt = ;
for(LL k = i + ; k <= n; k++) {
if(fr[k][j] == ) {
cnt++;
}
else {
break;
}
}
// val[i][j] - cnt
if(val[i][j] > cnt) {
add(s, id(i, j), val[i][j] - cnt, -cst[i][j]);
}
add(s, id(i, j), INF, cst[i][j]);
use += cst[i][j] * abs(val[i][j] - cnt);
}
if(fr[i][j] == || fr[i][j] == ) {
LL cnt = ;
for(LL k = j + ; k <= m; k++) {
if(fr[i][k] == ) {
cnt++;
}
else {
break;
}
}
if(v2[i][j] > cnt) {
add(id(i, j) + lm, t, v2[i][j] - cnt, -c2[i][j]);
}
add(id(i, j) + lm, t, INF, c2[i][j]);
use += c2[i][j] * abs(v2[i][j] - cnt);
}
if(fr[i][j] == ) {
LL a, b;
for(LL k = i - ; k >= ; k--) {
if(fr[k][j] == || fr[k][j] == ) {
a = id(k, j);
break;
}
}
for(LL k = j - ; k >= ; k--) {
if(fr[i][k] == || fr[i][k] == ) {
b = id(i, k) + lm;
break;
}
}
if(val[i][j] > ) {
add(a, b, val[i][j] - , -cst[i][j]);
}
add(a, b, INF, cst[i][j]);
use += cst[i][j] * abs(val[i][j] - );
}
}
} LL ans;
solve(s, t, ans);
ans += use; /*if(ans >= INF) {
puts("-1");
return 0;
}*/
for(int i = ; i <= top; i += ) {
if(abs(edge[i].len) == INF && (edge[i].c && edge[i ^ ].c)) {
puts("-1");
return ;
}
} printf("%lld", ans);
return ;
}
AC代码
思考：能否不转换为最小？好像无法判断是否合法...