解題區/解題區 - 其他題目

PTC 201504 D Bilibili's Railgun

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. Version 1
    2. 4.2. Version 2
    3. 4.3. Version 3
    4. 4.4. Version 4

Problem

科學超電磁砲 御坂美琴 (簡稱 Bilibili)，在學園都市中經常發生事件，每一個事件都會持續好幾天 [si, ei]，解決一個事件需要使用一次電磁砲。但是在一天中若使用 x 次，當天的消耗能量是 x * x (第 i 發能量為 2i - 1)。

為了解決所有事件，請問最少花費為多少。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
4
3
1 3
1 3
1 3
3
2 3
1 2
1 2
5
2 3
1 2
1 2
3 3
3 3
6
2 3
1 2
1 2
3 3
3 3
2 3

Sample Output

1
2
3
4
3
3
9
12

Solution

Version 1

這裡先提供一個 TLE 的作法，之後再來看看如何用增廣路徑的思路。

對這個問題，可以建造最少費用流模型，在點數不大的情況下可以運行，而這一題額外限制能量消耗的線性關係，最少費用流會因為邊數過多造成 TLE。

建造的方案如 source - event - (day, i) - sink，藉由滿流保證每個事件都會被解決，而每個 event 都指派到第 day 天的第 i 發，約束流量為 1 費用 2i - 1 到 sink，保證每一天使用的能量消耗不重複。

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
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <assert.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define MAXN 131072
#define MAXM (1048576<<2)
struct Node {
    int x, y, cap;
    double cost;// x->y, v
    int next;
} edge[MAXM];
int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
int dis[MAXN];
void addEdge(int x, int y, int cap, int cost) {
    assert(x < MAXN && y < MAXN && e < MAXM);
    edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
    edge[e].next = head[y], head[y] = e++;
}
int mincost(int s, int t, int n) {
    int mncost = 0;
    int flow, totflow = 0;
    int i, x, y;
    int oo = 0x3f3f3f3f;
    while (1) {
        for (int i = 0; i <= n; i++)
            dis[i] = oo;
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while (!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for (i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if (edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                    dis[y] = dis[x] + edge[i].cost;
                    pre[y] = x, record[y] = i;
                    if (inq[y] == 0) {
                        inq[y] = 1;
                        if (Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if (dis[t] == oo)
            break;
        flow = 0x3f3f3f3f;
        for (x = t; x != s; x = pre[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for (x = t; x != s; x = pre[x]) {
            int ri = record[x];
            edge[ri].cap -= flow;
            edge[ri^1].cap += flow;
            edge[ri^1].cost = -edge[ri].cost;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
int main() {
    int testcase, N, S[1024], E[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        int A[128] = {}, B[128] = {};
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &S[i], &E[i]);
            for (int j = S[i]; j <= E[i]; j++)
                A[j]++;
        }
        
        e = 0;
        memset(head, -1, sizeof(head));
        
        for (int i = 1; i <= 100; i++)
            B[i] = B[i-1] + A[i];
//        printf("%d\n", A[100]);
        int source = N + B[100] + 1, sink = N + B[100] + 2;
//        printf("source %d sink %d\n", source, sink);
        for (int i = 1; i <= 100; i++) {
//            printf("---- %d\n", A[i]);
            for (int j = 0, lj = B[i-1]; j < A[i]; j++, lj++) {
                addEdge(N + lj, sink, 1, j * 2 + 1);
                assert(N + lj < source);
//                printf("%d %d\n", N + lj, sink);
            }
        }
        for (int i = 0; i < N; i++) {
            addEdge(source, i, 1, 0);
            for (int j = S[i]; j <= E[i]; j++) {
                for (int k = 0, lk = B[j-1]; k < A[j]; k++, lk++) {
                    addEdge(i, N + lk, 1, 0);
                }
            }
        }
        
        int ret = mincost(source, sink, sink + 1);
        printf("%d\n", ret);
    }
    return 0;
}

Version 2

使用增廣路徑的想法，依序加入每一個 event 進來，移動 event 發生的時間。

當兩天原本的事件數 event[i] - event[j] = 1，那麼移動 event i 到另一天 j，總花費不會增加。接著可以保證，前 i 個 event 完成時，能夠移動 event 的情況 (直接或間接)，不會發生事件數差異大於等於 2！如果發生這種情況，則前 i 個事件的能量消耗不是最優解。

加入第 i+1 個事件，有機會發生可移動事件的天數之間的事件數差異大於等於 2，若發生這種情況，將其中一個事件移動到那一天執行。由於上述觀察，加入新的事件時，必然選擇可填入的最少能量消耗的日期，再去消除可以遞移的情況。否則會有一個更優解存在。

有沒有可能存在前 i-1 個事件不是最優解，加入第 i 個事件可以變成最優解？答案是否定的，既然不是最優解，一定存在事件數差異大於等於 2，藉由調整可以變得更小。

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
#include <stdio.h> 
#include <assert.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
using namespace std;
const int MAXN = 1024;
const int MAXD = 105;
struct Time {
    int st, ed;
    bool operator<(const Time &a) const {
        if (st != a.st)	
            return st < a.st;
        return ed < a.ed;
    }
} T[MAXN];
int visited[MAXD], match[MAXN];
vector<int> event[MAXD];
int event_move[MAXD][MAXD];
int dfs(int u, int place) {
    visited[u] = 1;
    if (event[u].size() < place - 1)
        return 1;
    for (int i = 1; i < MAXD; i++) {
        if (!visited[i]) {
            if (event_move[u][i] > 0) { // find a object to move i-day
                if (dfs(i, place)) {
                    int id = -1, id_pos = -1;
                    for (int j = 0; j < event[u].size(); j++) {
                        id = event[u][j], id_pos = j;
                        if (T[id].st <= i && i <= T[id].ed)
                            break;
                    }
                    assert(id >= 0);
                    for (int j = T[id].st; j <= T[id].ed; j++) {
                        event_move[u][j]--;
                        event_move[i][j]++;
                    }
                    match[id] = i;
                    event[u].erase(event[u].begin() + id_pos);
                    event[i].push_back(id);
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++)
            scanf("%d %d", &T[i].st, &T[i].ed);
        
        memset(event_move, 0, sizeof(event_move));
        for (int i = 0; i < MAXD; i++)
            event[i].clear();
        
        sort(T, T + N);
        for (int i = 0; i < N; i++) {
            int mn_day = T[i].st;
            for (int j = T[i].st; j <= T[i].ed; j++) {
                if (event[j].size() < event[mn_day].size())
                    mn_day = j;
            }
            
            match[i] = mn_day, event[mn_day].push_back(i);
            for (int j = T[i].st; j <= T[i].ed; j++) {
                event_move[mn_day][j]++;
            }			
            
            memset(visited, 0, sizeof(visited));
            dfs(mn_day, event[mn_day].size());
        }
        
        int ret = 0;
//		for (int i = 0; i < N; i++)
//			printf("%d\n", match[i]);
        for (int i = 1; i < MAXD; i++)
            ret += event[i].size() * event[i].size();
        printf("%d\n", ret);
    }
    return 0;
}

Version 3

費用流的做法不難、想法也很簡單，但是速度一直提升不上來，原因是邊數過多，費用流 O(VVE)，最暴力的費用流 E = 10^5、V = 10^5，病急投靠夢月來優化，由於費用流每次增廣流量都為 1，最後一層的邊使用跟回溯只會有兩種，因此將 (day, i) 的狀態縮小為 (day)，接著用特殊邊來可函數的邊花費 (？)，大幅度地降點後，終於來到 E = 10^5、V = 10^3。

深感欣慰的同時 TLE 也來報喜。

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <assert.h>
#include <algorithm>
using namespace std;
#define MAXN 2048
#define MAXM (526244)
struct Node {
    int x, y, cap;
    int cost;// x->y, v
    int next, sp;
} edge[MAXM];
int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
int dis[MAXN];
void addEdge(int x, int y, int cap, int cost, int sp) {
    assert(x < MAXN && y < MAXN && e < MAXM);
    if (sp == 0) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].sp = 0, edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].sp = 0, edge[e].next = head[y], head[y] = e++;
    } else {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].sp = sp, edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = cap, edge[e].cost = -cost;
        edge[e].sp = -sp, edge[e].next = head[y], head[y] = e++;
    }
}
int pass[MAXN];
int f(Node &e) {
    if (e.sp == 0)
        return e.cost;
    if (e.sp == 1)
        return e.cost * pass[e.x] * 2 + 1;
    if (e.sp == -1) {
        if (pass[e.y] == 0)
            return 0x3f3f3f3f;
        return -(e.cost * pass[e.y] * 2 + 1);
    }
    assert(false);
}
int mincost(int s, int t, int n) {
    int mncost = 0;
    int flow, totflow = 0, x, y;
    int INF = 0x3f3f3f3f;
    for (int i = 0; i < n; i++)
        pass[i] = 0;
    while (1) {
        for (int i = 0; i <= n; i++)
            dis[i] = INF;
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while (!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for (int i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                int ecost = f(edge[i]);
                if (edge[i].cap > 0 && dis[y] > dis[x] + ecost) {
                    dis[y] = dis[x] + ecost;
                    pre[y] = x, record[y] = i;
                    if (inq[y] == 0) {
                        inq[y] = 1;
                        if (Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if (dis[t] == INF)
            break;
        flow = INF;
        for (x = t; x != s; x = pre[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for (x = t; x != s; x = pre[x]) {
            int ri = record[x];
            if (edge[ri].sp == 0)
                edge[ri].cap -= flow;
            if (edge[ri^1].sp == 0)
                edge[ri^1].cap += flow;
                
            if (edge[ri].sp == 1)
                pass[edge[ri].x] ++;
            if (edge[ri].sp == -1)
                pass[edge[ri].y] --;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
const int MAXD = 105;
int main() {
    int testcase, N, S[1024], E[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        for (int i = 0; i < N; i++)
            scanf("%d %d", &S[i], &E[i]);
        
        e = 0;
        memset(head, -1, sizeof(head));
        
        int source = N + MAXD + 2, sink = N + MAXD + 3;
        for (int i = 0; i < N; i++) {
            addEdge(source, i, 1, 0, 0);
            for (int j = S[i]; j <= E[i]; j++)
                addEdge(i, N + j, 1, 0, 0);
        }
        
        for (int i = 1; i < MAXD; i++)
            addEdge(N + i, sink, 1, 1, 1);
        
        int ret = mincost(source, sink, sink + 1);
        printf("%d\n", ret);
    }
    return 0;
}

Version 4

既然思路明確，再努力觀察一下規則。

等著夢月弄出更高端的寫法，由於第一層的節點連接是一個區間，又因為邊 cost 都是單向往 sink 流去，回溯邊根本派不上用場，掃描線思路放進去找增廣路徑，速度有了突破性地進展。

根據區間的右端點排序，依序加入事件。每一次加入後往左掃描，當找到可以交換的日期時，把當時的工作抓出來擴充交換區間，擴充的區間只會往左端點增長。

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
#include <stdio.h> 
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 1024;
const int MAXD = 105;
struct Time {
    int st, ed;
    bool operator<(const Time &a) const {
        return ed < a.ed;
    }
} T[MAXN];
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++)
            scanf("%d %d", &T[i].st, &T[i].ed);
            
        sort(T, T + N);
        int ret = 0;
        int from[MAXD], assign[MAXN];
        set<int> event[MAXD];
        for (int i = 0; i < N; i++) {
            int l = T[i].st, r = T[i].ed;
            for (int j = r; j >= l; j--)                        // argument path
                from[j] = i;
            
            int day = r;    // choose
            for (int j = r; j >= l; j--) {
                if (event[j].size() < event[day].size())
                    day = j;
                if (event[day].size() == 0)
                    break;
                for (set<int>::iterator it = event[j].begin();
                    it != event[j].end(); it++) {
                    if (T[*it].st < l) {
                        for (int k = l-1; k >= T[*it].st; k--)  // argument path
                            from[k] = *it;
                        l = T[*it].st;
                    }
                }
            }
            
            ret += event[day].size() * 2 + 1;
            while (true) {
                int u = from[day];
                int d = assign[u];
                event[day].insert(u), assign[u] = day;
                if (u == i) break;
                event[d].erase(u), day = d;
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}