题意

有$n$张椅子一字排开，编号为$1-n$，一张椅子上只能坐$1$个人。其中$k(k \leq \lfloor \frac{n}{2} \rfloor)$张椅子上面坐着人，你需要使这$k$个人都挪到另外的椅子上，一次只能把一个人从他现在坐着的椅子$i$挪到另一张空椅子$j$上，代价为$|i-j|$。

求把这$k$个人都挪到另外的椅子上所需的最小总代价。

思路 - 各路神仙算法记录 :）

首先，第一眼看到这道题目，我想到的是一个二分图的匹配问题，已经被占的椅子作为一边，其他椅子作为另外一边，然后建图连边，两两配对。但是，我想要求出最小的代价，就需要想一想了。

（其实后面学了之后发现，是典型的$KM$算法求二分图最大权匹配问题，我傻了）

分析一下，由于$k \leq \lfloor \frac{n}{2} \rfloor$，因此一定存在一个解。然后，我们可以推断，一定存在一个最优解，椅子的状态改变不会超过一次，即不会有人把空椅子变成坐着人的椅子再变成空椅子。

也就是说，我们只要确定每个人最后能够到达哪个椅子，就能够得到最优解。二分图的做法貌似可以，但没那么好写。那么，想别的方向。直观上看起来是可以贪心的，排个序之后再选择最近的椅子？但是很快就把贪心给$hack$掉了，尝试添加一个反悔的操作，但好像在该题也不太适用，因为每个人都需要坐在新的椅子上。

（后面了解了模拟费用流之后，感觉有点像反悔贪心？）

回到最开始的图论想法，有点像最小费用最大流，超级源点连接已经被占的椅子，超级汇点连接其他椅子，流量为$1$，费用为$0$，限制最后的最小费用是从原有的$k$个人身上发出，从另外$n-k$个椅子上汇集。

现在需要找到一种连接椅子间的方式，把这个问题表示出来。为了表示代价，可以设相邻两个椅子的费用为$1$，容量设为$n$，这样能够表达第一张椅子到最后一张椅子的代价。

建图完毕，跑$Dinic$，最小费用最大流，时间复杂度理论最坏$O(n^2m)$？但是这题应该卡不到最坏复杂度。

但是，很不幸的，$TLE41$了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue> 
#define INF 1e9
#define maxn 1000005
using namespace std;
int n, a[maxn];
int S, T, k, head[maxn], vis[maxn];
struct Edge{
    int to;
    int cap;
    int next;
    int flow;
    int cost;
}Edge[maxn];
void Build(int u, int v, int cap, int cost, int flow){
    Edge[k].to = v;
    Edge[k].next = head[u];
    Edge[k].cap = cap;
    Edge[k].flow = flow;
    Edge[k].cost = cost;
    head[u] = k++;
}
/*dis->到该点的最小花费，pre->前一个点，last->前一个边*/
int dis[maxn], pre[maxn], last[maxn];
bool bfs(){
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 0; i <= k; i++)	Edge[i].flow = INF;
    queue<int> q1;
    q1.push(S);		vis[S] = 1;
    pre[T] = 0;		dis[S] = 0;
    while(!q1.empty())
    {
        int tmp = q1.front(); q1.pop();	vis[tmp] = 0;
        for(int i = head[tmp]; ~i; i = Edge[i].next)
        {
            if(Edge[i].cap > 0 && dis[Edge[i].to] > dis[tmp] + Edge[i].cost)
            {
                dis[Edge[i].to] = dis[tmp] + Edge[i].cost;
                pre[Edge[i].to] = tmp;			
                last[Edge[i].to] = i;
                Edge[Edge[i].to].flow = min(Edge[tmp].flow, Edge[i].cap);
                if(!vis[Edge[i].to])
                {
                    vis[Edge[i].to] = 1;
                    q1.push(Edge[i].to);
                }
            } 
        }
    }
    return pre[T];
}
int Dinic(){
    int maxflow = 0, mincost = 0;
    while(bfs())
    {
        int tmp = T;
        maxflow += Edge[T].flow;
        mincost += Edge[T].flow * dis[T];
        while(tmp != S)
        {
            Edge[last[tmp]].cap -= Edge[T].flow;
            Edge[last[tmp]^1].cap += Edge[T].flow;
            tmp = pre[tmp];
        }
    }
    return mincost;
}
int main(void)
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    S = 0; T = n + 1;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i] == 1)
        {
            Build(S, i, 1, 0, 0);
            Build(i, S, 0, 0, 0); 
        }
        else
        {
            Build(i, T, 1, 0, 0);
            Build(T, i, 0, 0, 0); 
        }
        if(i != n)
        {
            Build(i, i + 1, n, 1, 0);
            Build(i + 1, i, 0, -1, 0);
            
            Build(i + 1, i, n, 1, 0);
            Build(i, i + 1, 0, -1, 0);
        }
    }
    int ans = Dinic();
    printf("%d\n", ans);
    return 0;
}

由于代码是拿我很早以前的模板改的所以有点丑。

下面开始半懂不懂，仅供记录，主要是为自己学习留个底（

然后我百度了一下，发现有人推荐使用$zkw$费用流…在某些情况下跑的飞快（雾

我找了个板子（板子入口），测试了一下，确实飞快跑过了…

据说在费用范围较小，流量较大，或者增广路径比较短的图中，使用$zkw$费用流有明显提速，反之则$zkw$费用流可能比原始费用流更慢（出处见下一解法的文档）。

以后在专门写一篇总结一下网络流（

这道题只要建完边就只剩下选择算法的问题了（

这一题也可以使用$KM$来做，实际上，$KM$解决的就是这样的二分图最大权匹配问题（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
bool vis[200001];
int dist[200001];                                                            //vis是spfa访问标记及増广访问标记,dist是每个点距离标号
int n, m, s, t, ans = 0;                                                     //s是起点，t是终点，ans是费用答案
int nedge = -1, p[200001], c[200001], cc[200001], nex[200001], head[200001]; //nedge为边编号
//p,c,cc,nex表编号为i的边终点,流量,费用,下一条边，head表编号为i的点射出的最后一边
void addedge(int x, int y, int z, int zz)
{
    p[++nedge] = y;
    c[nedge] = z;
    cc[nedge] = zz;
    nex[nedge] = head[x];
    head[x] = nedge;
} //建边（数组模拟边表倒挂）
bool spfa(int s, int t)
{
    memset(vis, 0, sizeof vis); //深搜前先清0
    for (int i = 0; i <= n; i++)
        dist[i] = 1e9;
    dist[t] = 0;
    vis[t] = 1; //SPFA维护距离标号要倒着跑，维护出到终点的最短路径
    deque<int> q;
    q.push_back(t); //使用了SPFA的队列优化
    while (!q.empty())
    {
        int now = q.front();
        q.pop_front();
        for (int k = head[now]; k > -1; k = nex[k])
        { //下一行的k^1可保证正流
            if (c[k ^ 1] && dist[p[k]] > dist[now] - cc[k])
            {                                   //SPFA倒着跑故c[k]对应反向边是为正
                dist[p[k]] = dist[now] - cc[k]; //已经倒着，建边时反向边权为负，故负负得正
                if (!vis[p[k]])
                {
                    vis[p[k]] = 1;
                    if (!q.empty() && dist[p[k]] < dist[q.front()])
                        q.push_front(p[k]);
                    else
                        q.push_back(p[k]); //距离最短的放前面，否则放队末
                }
            }
        }
        vis[now] = 0; //此点搜完退出就要清0
    }
    return dist[s] < 1e9; //判断起点终点是否连通
}
int dfs(int x, int low)
{ //这里就是进行増广了
    if (x == t)
    {
        vis[t] = 1;
        return low;
    }
    int used = 0, a;
    vis[x] = 1; //类似dinic
    for (int k = head[x]; k > -1; k = nex[k])
        if (!vis[p[k]] && c[k] && dist[x] - cc[k] == dist[p[k]])
        {                                         //未访问,有流量,此边在最短路径上
            a = dfs(p[k], min(c[k], low - used)); //往下一个点深搜且流量降低
            if (a)
                ans += a * cc[k], c[k] -= a, c[k ^ 1] += a, used += a; //深搜有流：加钱,减流,加流,递归流
            if (used == low)
                break; //流量流完了可以退出（本题可忽略）
        }              //这题最大流不定,故开了1E9无限大
    return used;
}

int costflow()
{                 //开始跑
    int flow = 0; //开始时流量为0
    while (spfa(s, t))
    {               //判断起点终点是否连通，不连通则满流退出
        vis[t] = 1; //只是为了第一次可以进入vis
        while (vis[t])
        {
            memset(vis, 0, sizeof vis); //先清零，看下面的深搜能否更新到终点
            flow += dfs(s, 1e9);        //一直増广直到走不到为止
        }
    }
    return flow; //返回最大流，费用在ans里
}
int a[5005];
int main()
{
    memset(nex, -1, sizeof nex);
    memset(head, -1, sizeof head);     //初始化nex与head数组
    scanf("%d", &n);
    s = 0; t = n + 1;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i] == 1)
            addedge(s, i, 1, 0), addedge(i, s, 0, 0);
        else
            addedge(i, t, 1, 0), addedge(t, i, 0, 0);
        if(i != n)
            addedge(i, i + 1, n, 1), addedge(i + 1, i, 0, -1),
            addedge(i + 1, i, n, 1), addedge(i, i + 1, 0, -1);
    }
    costflow();
    printf("%d", ans); //输入最大流时流量与费用
    return 0;
}

而后，我在$Codeforces$评论区，还看到有一种模拟费用流的做法：

image-20210611192049402

具体做法见该文档$Problem \ 2$：模拟费用流问题 陈江伦

本题$O(n)$解法如下（来自$Codeforces$评论区，出处见代码顶部）：

image-20210611200548160

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
    author:  Maksim1744
    created: 18.05.2021 21:05:42
*/

#include "bits/stdc++.h"

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    vector<int> sum0(n), sum1(n);
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) sum0[i] = i;
        else sum1[i] = i;
    }
    for (int i = 1; i < n; ++i) {
        sum0[i] += sum0[i - 1];
        sum1[i] += sum1[i - 1];
    }

    auto get_sum = [&](int l, int r) {
        if (l > r) return 0;
        int s0 = sum0[r] - (l == 0 ? 0 : sum0[l - 1]);
        int s1 = sum1[r] - (l == 0 ? 0 : sum1[l - 1]);
        return abs(s0 - s1);
    };

    vector<int> dp(n, 1e9);

    // offset for negative balance
    int N = n;
    vector<int> with_balance(N * 2 + 1, -1);

    int balance = N + 0;
    with_balance[N + 0] = 0;

    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) --balance;
        else ++balance;
        if (with_balance[balance] != -1) {
            int l = with_balance[balance];
            int r = i;
            int sm = get_sum(l, r);
            // type 2 edge
            dp[r] = min(dp[r], sm + (l == 0 ? 0 : dp[l - 1]));
        }
        with_balance[balance] = i + 1;
        if (a[i] == 0) {
            // type 1 edge
            dp[i] = min(dp[i], (i == 0 ? 0 : dp[i - 1]));
        }
    }

    cout << dp.back() << '\n';

    return 0;
}

同样是模拟费用流，还有个$O(nlogn)$解法，没有那么抽象。

摘自Educational Codeforces Round 109 (Div. 2)] 解题报告 | 赤红幻想 (reimu.red)

（个人感觉有点像反悔贪心？）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
const int MAXN = 5005;
int n, m;
struct node
{
    int op;    //1是洞，0是老鼠
    ll x, lim; //x是位置，lim是洞的容量上限
} a[N];
priority_queue<ll, vector<ll>, greater<ll>> s1;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> s2;
inline void solve()
{
    int o;
    int tot = 0;
    scanf("%d", &o); //n为洞的个数，m为老鼠个数
    for (int i = 1, p, x = 1; i <= o; ++i, ++x)
    {
        scanf("%d", &p);
        if (p == 1)
            a[++tot] = {0, x, 0}, ++n;
        else
            a[++tot] = {1, x, 1}, ++m;
    }
    // for (int i = 1, x; i <= n; ++i)
    //     scanf("%d", &x), a[++tot] = {1, x, 1};
    // for (int i = 1, x; i <= m; ++i)
    //     scanf("%d", &x), a[++tot] = {0, x, 0};
    a[++tot] = {1, -llinf, m}, a[++tot] = {1, llinf, m};
    sort(a + 1, a + tot + 1, [&](auto x, auto y) { return x.x < y.x; });
    ll ans = 0;
    for (int i = 1; i <= tot; ++i)
    {
        if (a[i].op == 1)
        {
            int li = a[i].lim;
            while (!s1.empty() && li && s1.top() + a[i].x < 0)
            {
                li--;
                ans += s1.top() + a[i].x;
                s2.push({-s1.top() - 2 * a[i].x, 1});
                s1.pop();
            }
            if (li)
                s2.push({-a[i].x, li});
        }
        else
        {
            auto tmp = s2.top();
            s2.pop();
            ans += tmp.first + a[i].x;
            s1.push({-tmp.first - 2 * a[i].x});
            tmp.second--;
            if (tmp.second)
                s2.push(tmp);
        }
    }
    cout << ans << endl;
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

经历了这么多图论做法，我发现，$dp$的做法是多么美妙（

设$dp[i][j]$，为前$i$个人，安排在前$j$个椅子被成功处理的最小代价（

为了使得处理得到的是最小代价，初始化为极大值。

然后，分析边界情况，$dp[0][j] =0$，$dp[i][0] = inf$。

考虑转移方程，分两种情况：

  1. $dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(b[i] - c[j]))$，把第$i$个人移动到第$j$个椅子上。
  2. $dp[i][j] = min(dp[i][j], dp[i][j - 1])$，前$i$个人在前$j-1$的椅子上被安排好了。

由此进行转移即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx", "sse2")
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
int n, a[maxn], dp[maxn][maxn];
int b1, b[maxn], c1, c[maxn];
int main(void)
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[i] == 0 ? c[++c1] = i : b[++b1] = i;
    }
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 0; i <= c1; i++)    dp[0][i] = 0;
    for(int i = 1; i <= b1; i++)
    {
        for(int j = i; j <= c1; j++)
        {
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(b[i] - c[j]));
            dp[i][j] = min(dp[i][j], dp[i][j - 1]);
        }
    }
    printf("%d\n", dp[b1][c1]);
    return 0;
}

结尾

$wsfw$

本篇”题解“不像往常主要记录了自己的思路，而是记录了各位大佬的写法，比较水，主要是先记录下来帮助自己学习。

希望有朝一日我的博客也会被人引用（