THUSCH 2017 换桌（费用流，线段树优化建图）
yanchengzhi · · 题解
THUSCH 2017 换桌（费用流，线段树优化建图）
二分图带权匹配，可以用费用流解决。
首先有个很明显的连边方式，每个人向能去的座位连边，边数是
考虑优化一下建图方式。
可以把桌子编号的移动和位置编号的移动分开考虑。
建立
然后发现桌子编号的移动是一段区间，因此可以使用线段树优化建图，这样边数可以优化到
考虑继续优化，发现位置编号的移动可以连成一个环的形式，这样就可以把边数优化到
#include <bits/stdc++.h>
typedef long long ll;
const int inf = 1e9;
namespace MCMF {
const int maxN = 1e5;
const int maxM = 1e6;
int S, T, n, tot, maxflow, mincost;
int head[maxN], now[maxN], dis[maxN];
bool vis[maxN];
struct edge {
int to, nxt;
int f, c;
} e[maxM];
void add(int u, int v, int f, int c) {
e[++tot].to = v;
e[tot].nxt = head[u];
e[tot].f = f;
e[tot].c = c;
head[u] = tot;
}
void add2(int u, int v, int f, int c) {
add(u, v, f, c);
add(v, u, 0, -c);
}
bool spfa() {
for(int i = 1; i <= n; i++) {
dis[i] = inf;
vis[i] = 0;
}
std::deque<int> q;
q.push_back(S);
dis[S] = 0;
vis[S] = 1;
while(!q.empty()) {
int u = q.front();
q.pop_front();
vis[u] = 0;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to, f = e[i].f, c = e[i].c;
if(f && dis[u] + c < dis[v]) {
dis[v] = dis[u] + c;
if(!vis[v]) {
if(!q.empty() && dis[v] < dis[q.front()]) {
q.push_front(v);
}
else {
q.push_back(v);
}
vis[v] = 1;
}
}
}
}
return dis[T] < inf;
}
int dfs(int u, int flow) {
if(u == T) {
return flow;
}
int res = 0;
vis[u] = 1;
for(int &i = now[u]; i; i = e[i].nxt) {
int v = e[i].to, c = e[i].c, f = e[i].f;
if(dis[v] == dis[u] + c && f && !vis[v]) {
int t = dfs(v, std::min(flow, f));
if(t) {
flow -= t;
res += t;
mincost += t * c;
e[i].f -= t;
e[i ^ 1].f += t;
}
else {
dis[v] = -inf;
}
if(!flow) {
break;
}
}
}
vis[u] = 0;
return res;
}
void mcmf() {
while(spfa()) {
for(int i = 1; i <= n; i++) {
vis[i] = 0;
now[i] = head[i];
}
maxflow += dfs(S, inf);
}
}
void init(int x) {
n = x;
S = n - 1;
T = n;
tot = 1;
for(int i = 1; i <= n; i++) {
head[i] = 0;
}
}
}
using MCMF::S;
using MCMF::T;
using MCMF::add2;
using MCMF::maxflow;
using MCMF::mincost;
using namespace std;
const int maxn = 305;
int n, m, cnt, l[maxn][maxn], r[maxn][maxn];
int id(int x, int y) {
return (x - 1) * m + y;
}
#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid ((l + r) >> 1)
struct SGT {
int num[maxn * 4], leaf[maxn];
void build_pre(int x, int l, int r) {
num[x] = ++cnt;
if(l == r) {
leaf[l] = cnt;
return;
}
build_pre(lc, l, mid);
build_pre(rc, mid + 1, r);
}
void build(int x, int l, int r) {
if(l == r) {
return;
}
add2(num[x], num[lc], inf, 0);
add2(num[x], num[rc], inf, 0);
build(lc, l, mid);
build(rc, mid + 1, r);
}
void link(int x, int l, int r, int L, int R, int u, int f, int c) {
if(L > R || l > R || r < L) {
return;
}
if(l >= L && r <= R) {
add2(u, num[x], f, c);
return;
}
link(lc, l, mid, L, R, u, f, c);
link(rc, mid + 1, r, L, R, u, f, c);
}
} A[11], B[11];
#undef lc
#undef rc
#undef mid
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> l[i][j];
l[i][j]++;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> r[i][j];
r[i][j]++;
}
}
/*
O(nm(m + log n))
cnt = n * m * 3;
for(int i = 1; i <= m; i++) {
A[i].build_pre(1, 1, n);
B[i].build_pre(1, 1, n);
}
MCMF::init(cnt + 2);
for(int i = 1; i <= m; i++) {
A[i].build(1, 1, n);
B[i].build(1, 1, n);
}
for(int i = 1; i <= n * m; i++) {
add2(S, i, 1, 0);
add2(i, i + n * m, 1, 0);
add2(i + n * m * 2, T, 1, 0);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
for(int k = 1; k <= m; k++) {
add2(A[j].leaf[i], id(i, k) + n * m * 2, inf, min(abs(j - k), m - abs(j - k)) + i * 2);
add2(B[j].leaf[i], id(i, k) + n * m * 2, inf, min(abs(j - k), m - abs(j - k)) - i * 2);
}
if(l[i][j] >= i) {
A[j].link(1, 1, n, l[i][j], r[i][j], id(i, j) + n * m, 1, -i * 2);
}
else if(r[i][j] <= i) {
B[j].link(1, 1, n, l[i][j], r[i][j], id(i, j) + n * m, 1, i * 2);
}
else {
A[j].link(1, 1, n, i, r[i][j], id(i, j) + n * m, 1, -i * 2);
B[j].link(1, 1, n, l[i][j], i - 1, id(i, j) + n * m, 1, i * 2);
}
}
}
*/
// O(nm log n)
cnt = n * m * 2;
for(int i = 1; i <= m; i++) {
A[i].build_pre(1, 1, n);
B[i].build_pre(1, 1, n);
}
MCMF::init(cnt + 2);
for(int i = 1; i <= m; i++) {
A[i].build(1, 1, n);
B[i].build(1, 1, n);
}
for(int i = 1; i <= n * m; i++) {
add2(S, i, 1, 0);
add2(i + n * m, T, 1, 0);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int L = j - 1 > 0 ? j - 1 : m, R = j + 1 <= m ? j + 1 : 1;
add2(A[j].leaf[i], A[L].leaf[i], inf, 1);
add2(A[j].leaf[i], A[R].leaf[i], inf, 1);
add2(B[j].leaf[i], B[L].leaf[i], inf, 1);
add2(B[j].leaf[i], B[R].leaf[i], inf, 1);
add2(A[j].leaf[i], id(i, j) + n * m, inf, i * 2);
add2(B[j].leaf[i], id(i, j) + n * m, inf, -i * 2);
if(l[i][j] >= i) {
A[j].link(1, 1, n, l[i][j], r[i][j], id(i, j), 1, -i * 2);
}
else if(r[i][j] <= i) {
B[j].link(1, 1, n, l[i][j], r[i][j], id(i, j), 1, i * 2);
}
else {
A[j].link(1, 1, n, i, r[i][j], id(i, j), 1, -i * 2);
B[j].link(1, 1, n, l[i][j], i - 1, id(i, j), 1, i * 2);
}
}
}
MCMF::mcmf();
if(maxflow < n * m) {
cout << "no solution\n";
}
else {
cout << mincost << '\n';
}
return 0;
}