這題要求調整部分邊的方向，把有環的有向圖中部分邊反向，使其變成無環圖，我們要求的是調整的邊的最大權值最小的方案。首先我們要知道一個原理，如果無環圖加入$A \to B$會使其變爲有環圖，那麼$B\to A$一定是連通的，那麼加入邊$B\to A$不會使其成環。那麼，我們刪掉某些邊得到無環圖之後，必然可以加回來得到無環圖。而如果我們刪除權值不大於ans的所有邊，我們可以很快地算出是否有環。如果有環，則ans一定小於答案，如果無環，則ans不小於答案。根據這一性質，我們可以二分套判環解決，判環使用拓撲方法，複雜度爲$O((m+n)logM)M$可以是最大邊權，也可以是邊權的中位數（$O(n)$找中位數要多寫不少代碼，並且這題不必要）
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
int v, w;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, M = 0;
cin >> n >> m;
vector<E> path[n + 1];
FOR(i, 0, m) {
int u, v, w;
cin >> u >> v >> w;
M = max(M, w);
path[u].push_back({v, w});
}
int ans = M / 2;
int tmp[2] = {0, M};
do {
vector<E> pathcpy[n + 1];
int cnt[n + 1];
RST(cnt);
FOR(i, 1, n + 1) for (auto p : path[i]) if (p.w > ans) {
pathcpy[i].push_back(p);
++cnt[p.v];
}
queue<int> q;
FOR(i, 1, n + 1) if (!cnt[i]) q.push(i);
int c = 0;
while (!q.empty()) {
++c;
int now = q.front();
q.pop();
for (auto p : pathcpy[now]) {
--cnt[p.v];
if (!cnt[p.v]) q.push(p.v);
}
}
tmp[c == n] = ans + (c != n);//有環時答案大於ans，可以從ans+1開始
ans = ((ll)tmp[0] + tmp[1]) / 2;
} while (tmp[1] != tmp[0]);
cout << ans;
}
|
這題是求免費一條邊的最小生成樹權值和，以及要使權值和等於該值的情況下，可以選擇的免費邊的數量。首先，最小生成樹的算法這裏不再累述，kruskal算法即可。然後根據貪心的思想易知第一個問題的答案爲最小生成樹總權值-最小生成樹上最大邊權值。然後難點就在於第二個問題。樹上權值最大的邊（可能有多條相等）如果能被另一條邊替代，那麼替代後免費新的邊，也能得到相同的結果。所以我們要找到可以替換樹上最大邊的邊。我們可以把最大邊去掉（第一次並查集記錄最大邊條數，第二次並查集參考G題），這樣樹就出現了中斷，然後我們需要尋找能夠把中斷補上的邊。我們沿用kruskal算法的並查集，即可輕鬆判斷一條邊是否能補上中斷。遍歷一遍邊即可，由最小生成樹的性質，小邊不可能替代大邊，所以權值小於樹上最大邊的邊可以直接略過。
最大部分的時間複雜度就是kruskal的時間複雜度，即$O(mlogm+mA(n)+n)$，其實複雜度最大的地方就是排序邊的O(mlogm)
代碼及註釋：
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int fa[100001], depth[100001];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
u = find(u), v = find(v);
if (depth[u] > depth[v])
fa[v] = u;
else {
fa[u] = v;
if (depth[v] == depth[u]) ++depth[v];
}
}
struct E {
int u = 0, v = 0, w = 0;
bool operator<(E x) const { return w < x.w; }
};
E edge[200005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int M = 0, n, m, i = 0, cm = 0;
ll S = 0;
cin >> n >> m;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
edge[i] = {u, v, w};
}
sort(edge, edge + m);
for (auto p : edge)//第一次並查集
if (i == n - 1)
break;
else if (find(p.u) == find(p.v))
continue;
else {
++i;
connect(p.u, p.v);
S += p.w;
if (p.w > M) {
M = p.w;
cm = 1;
} else if (p.w == M)
++cm;//記錄樹上最大邊的條數
}
for (int i = 1; i <= n; ++i) fa[i] = i;
RST(depth);
int cnt = i = 0;
for (auto p : edge)
if (i == n - 1 - cm)//跳過樹上最大邊
break;
else if (find(p.u) == find(p.v))
continue;
else {
++i;
connect(p.u, p.v);
}
for (auto p : edge)//如果想進一步優化，可以保留第二次並查集的最後位置，然後從該位置-cm開始
if (p.w >= M && find(p.u) != find(p.v)) ++cnt;
cout << S - M << ' ' << cnt;
}
|
該題判斷是否有歐拉路徑，然後輸出字典序最小的歐拉路徑。判斷歐拉路徑根據出入度，所有點入度等於出度則有歐拉回路，入度比出度大一的點和出度比入度大一的點各一個（必須兩者都有一個）則有歐拉路徑（非迴路）。然後是輸出部分，如果是迴路，要從有路的最小點作爲起點。然後可以用一個dfs，從小的邊開始搜，回溯的時候即可得到反向的歐拉路徑，再反向輸出即可。由於路徑可能很長，搜索深度可能很深，dfs遞歸會發生棧溢出，可以加inline內聯交給GNU的強大力量去解決（這樣寫甚至跑起來更快），也可以寫非遞歸版的dfs（碼量稍大）。複雜度$O(m)$
代碼及註釋：
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int n, m, ans[2000005], pos = 0, cnt = 0;
vector<int> path[1000005];
inline void dfs(int s) {//遞歸版
while (!path[s].empty()) {
int p = path[s].back();
path[s].pop_back();
dfs(p);
ans[cnt++] = p;
}
}
void dfs(int s) {//非遞歸版
int stack[2000005], top = 0;
stack[++top] = s;
while (top) {
int x = stack[top];
if (path[x].empty()) {
top--;
ans[cnt++] = x;
} else {
stack[++top] = path[x].back();
path[x].pop_back();
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int i[n + 1], o[n + 1];
RST(i);
RST(o);
FOR(j, 0, m) {
int u, v;
cin >> u >> v;
path[u].push_back(v);
++i[v], ++o[u];
}
int s = 0, t = 0;
FOR(j, 1, n + 1) {
if (o[j] == i[j])
continue;
else if (o[j] - i[j] == 1) {
if (s) goto shame;
s = j;
} else if (o[j] - i[j] == -1) {
if (t) goto shame;
t = j;
} else
goto shame;
}
if ((bool)s ^ (bool)t) goto shame;
for (auto &p : path) sort(p.begin(), p.end(), greater<int>());
if (!s)
while (!o[++s])
;
dfs(s);
//遞歸版起點要單獨輸出一下 cout << s << ' ';
while (cnt) cout << ans[--cnt] << ' ';
return 0;
shame:
cout << "What a shame!";
}
|
這題要求的是在一個有向，可能有環的正點權圖上獲取最大值。如果它是無環的，那麼以終點的權作爲邊權求最長路即可（無環圖不會到達一個點多次），因此，我們就考慮怎麼處理環。這樣就引入了縮點的概念(據說暴力也可以過?)，爲了獲取最大權，進入環中一個點後必然會把整個環喫完，然後從中選擇合適的點出環。根據這一性質，我們可以找到圖中的環（不一定是單層的環，標準的名稱爲強聯通分量），把每一個環縮成一個點，權值爲各點權值之和，環內點與環外點的路徑都加在縮成的點上。實現的方法有Kosaraju、Tarjan（沒錯，又是這位圖靈獎巨佬）等。本題以Kosaraju爲例，從起點開始進行一次dfs，回溯時按順序記錄點，再在反向圖上，按之前的記錄逆序一次dfs，在第i次反向dfs中初次找到的點（當然，正向dfs中不可達的點要排除）就構成了第i個強聯通分量。然後建立新圖，按一開始說的無環圖做法即可，正權圖最長路相當於負權圖最短路，使用spfa算法求解。Kosaraju的複雜度通常爲$O(n+m)$，時間瓶頸在於spfa，複雜度最壞可達$O(mn)$
代碼及註釋：
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
int v, l;
};
vector<int> path[3001], repath[3001];
int m, n, l[3001], dfn[3001], pos = 0, vis[3001], revis[3001], f[3001], point[3001], s, p[3001], dis[3001];
vector<E> fpath[3001];
inline void dfs(int now) {//正向dfs
vis[now] = 1;
for (auto &p : path[now])
if (!vis[p]) dfs(p);
dfn[pos++] = now;
}
inline void redfs(int now, int pos) {//反向dfs
if (!vis[now] || revis[now]) return;
revis[now] = 1;
f[now] = pos;
point[pos] += l[now];
for (auto &p : repath[now]) redfs(p, pos);
}
void spfa() {
RST(dis);
queue<int> q;
dis[f[s]] = point[f[s]];
q.push(f[s]);
bool has[3001] = {0};
has[f[s]] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
has[now] = 0;
for (auto p : fpath[now])
if (dis[p.v] < dis[now] + p.l) {
dis[p.v] = dis[now] + p.l;
if (!has[p.v]) {
q.push(p.v);
has[p.v] = 1;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int u[m], v[m];
FOR(i, 0, m) {
cin >> u[i] >> v[i];
path[u[i]].push_back(v[i]);
repath[v[i]].push_back(u[i]);//反向圖
}
FOR(i, 1, n + 1) cin >> l[i];
int np;
cin >> s >> np;
FOR(i, 0, np) cin >> p[i];
RST(vis);
dfs(s);
int tmp = pos;
pos = 0;
RST(revis);
for (int i = tmp - 1; i >= 0; --i) redfs(dfn[i], pos++);
FOR(i, 0, m)
if (f[u[i]] != f[v[i]])
fpath[f[u[i]]].push_back({f[v[i]], point[f[v[i]]]});//建立縮點後的新圖
spfa();
int M = 0;
FOR(i, 0, np) M = max(M, dis[f[p[i]]]);
cout << M;
}
|
這是本次的簽到題，解題方法是根據貪心的思想，按權值從小到大取邊，同時採用並查集判斷邊是否可取，這種算法被稱爲
kruskal算法，複雜度爲$O(mlogm+mA(n)+n)$，瓶頸是邊排序的$O(mlogm)$
代碼：
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
|
#include <bits/stdc++.h>
using namespace std;
int fa[1001], depth[1001];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
u = find(u), v = find(v);
if (depth[u] > depth[v])
fa[v] = u;
else {
fa[u] = v;
if (depth[v] == depth[u]) ++depth[v];
}
}
struct E {
int u, v, w;
bool operator<(E x) const { return w < x.w; }
};
E edge[500000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k, pos = 0;
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
edge[i] = {u, v, w};
}
sort(edge, edge + m);
int result = 0;
for (auto p : edge)
if (n == k)
break;
else if (find(p.u) == find(p.v))
continue;
else {
connect(p.u, p.v);
--n;
result += p.w;
}
cout << result;
}
|
這題的思路沒有什麼好說的，很明顯的網絡流板題。下面簡單說一下網絡流（以後有時間可能會單獨寫一篇博客，也很可能會鴿）
網絡流是一個有若干條帶權（容量）邊組成的，固定源點和匯點的有向圖。本題要解決的是，從源點產生的流（本題中水流是個很形象的例子），經過各邊彙集到匯點，這樣的流的最大流量。顯然，對於每個點，流入流出的量相等，總流量守恆；同時，每條邊上的流量均不能超過該條邊的容量。在思考怎麼求出最大流的過程中，我們要了解一個非常重要的定理──增廣路定理。當我們找到網絡流中一條從源點到匯點的通路時，可以把這條通路的各段邊的容量減少一個值 $a$，最好的情況下下，這樣處理後的網絡的最大流就減少了 $a$，這樣的網絡我們稱之爲殘量（殘留容量）網絡，當殘量網絡中沒有上述通路時，殘量網絡的最大流爲0，原網絡的最大流爲$\sum a$，我們可以利用dfs找通路，$a$ 取路徑上的最小殘量，不斷循環得出結果。
然而，這樣做會存在一些問題
1.每次找到的路徑可以是最好的路連接徑嗎？似乎不是。這種情況我們在數據結構專題的K題（點此進入）中遇到過，當時我們在刪點的時候加入新的點來模擬反悔的操作。這裏我們也可以加入反向邊來模擬反悔的操作。
2.這樣反覆的dfs很耗時，可能會反覆搜某一條邊，尤其是各邊容量的極差很大時。該算法稱爲Ford-Fulkerson算法，複雜度爲$O(mC)$，通常只建議用來處理容量很小的圖，如單位容量簡單網絡最大流的快速算法（其實我並不會）的其中部分步驟可以用它。可以採用bfs，即Edmonds-Karp算法來改進，複雜度爲$O(nm^2)$。但是EK算法過這題似乎有點緊，有沒有更快的做法？dinic、ISAP、等（其實兩者原理很像，優化魔改之後界限並不是那麼清晰）。
我們把所有的節點根據與源點的距離分層，找增廣路時只取依層遞進的路徑，然後再重新分層，反覆循環。複雜度最大爲$O(mn^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
|
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
int e, c;
};
int n, m, cur[201], tail = 0, depth[201];
bool visited[201];
edge edges[20001];
vector<int> path[201];
inline void addedge(int s, int e, int c) {//建圖時把反向邊位置也分配好，並且分配到正向邊位置^1，便於快速找反向邊
edges[tail] = {e, c};
path[s].push_back(tail++);
edges[tail] = {s, 0};
path[e].push_back(tail++);
}
bool dinic_bfs() {//通過bfs，逐層外擴，實現分層
RST(depth);
RST(visited);
visited[1] = 1;
queue<int> q;
q.push(1);
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto p : path[now]) {
if (!visited[edges[p].e] && edges[p].c) {
depth[edges[p].e] = depth[now] + 1;
q.push(edges[p].e);
visited[edges[p].e] = 1;
}
}
}
return visited[n];//如果匯點已不可達，說明已無增廣路，則結束循環，否則繼續
}
int dinic_dfs(int now, int cap) {
if (now == n || !cap) return cap;
for (auto &i = cur[now]; i < path[now].size(); ++i) {//加入cur數組實現當前弧優化，搜到每條點時之前已被搜過的點不會搜出新的增廣路路徑，因此可以直接跳過。
auto &p = path[now][i];
if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
edges[p].c -= tmp;
edges[p ^ 1].c += tmp;//反向邊加上相同的值，後面可以走這條反向邊來反悔之前選的邊
if (tmp) return tmp;//找到有值的增廣路，返回
}
}
depth[now] = -1;
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
while (m--) {
int s, e, c;
cin >> s >> e >> c;
addedge(s, e, c);
}//首先建圖
int result = 0;
while (dinic_bfs()) {//然後開始跑分層
RST(cur);
int tmp;
while ((tmp = dinic_dfs(1, INT_MAX >> 2))) result += tmp;//再在圖中跑符合要求的增廣路，找不到了就重新分層
}
cout << result;
}
|
這是一道很裸的有向圖（無向圖拆邊，然後做法也一樣）K短路問題，我們可以採用一個方向最短路算法初始化（dijkstra，spfa什麼的都可以，時間很鬆），一個方向A*啓發式搜索（這類題是$h(x)=h*(x)$的特例）的方法解題。最短路算法不再多說，對於A*算法，我們用一個優先隊列，從起點開始，每次擴展其直接可達的邊入隊，這樣的過程中，跑出i次第i短路時，它可以擴展出i+1次第i+1短路，由此，當某條邊出隊K次時可以終止，此時的路徑長度就是第k短路的長度。複雜度（貌似）$O(kmlogm)$
代碼及註釋
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
int v;
ll w;
};
struct status {
int p;
ll l;
bool operator<(status b) const { return l > b.l; }
};
struct astar {
int v;
ll g, f;
bool operator<(astar b) const { return f == b.f ? g > b.g : f > b.f; }
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k, s, t;
cin >> n >> m >> k >> s >> t;
vector<edge> path[n + 1], repath[n + 1];
ll dis[n + 1];
int visited[n + 1];
for (int i = 0; i < m; ++i) {//建立正向圖和反向圖
int u, v, w;
cin >> u >> v >> w;
path[u].push_back({v, w});
repath[v].push_back({u, w});
}
memset(dis, 0x3f, sizeof(dis));
memset(visited, 0, sizeof(visited));
priority_queue<status> q;
dis[t] = 0;
q.push({t, 0});
while (!q.empty()) {//反向dijkstra算法求最短路，預處理出h(x)
status now = q.top();
q.pop();
if (visited[now.p]) continue;
visited[now.p] = 1;
for (auto &p : repath[now.p]) {
if (dis[p.v] > dis[now.p] + p.w) {
dis[p.v] = dis[now.p] + p.w;
q.push({p.v, dis[p.v]});
}
}
}
memset(visited, 0, sizeof(visited));
priority_queue<astar> paths;//然後正向通過A*算法得出結果
paths.push({s, 0, dis[s]});
while (!paths.empty()) {
astar now = paths.top();
paths.pop();
if (++visited[now.v] == k && now.v == t) {
cout << now.f;
return 0;
};
if (visited[now.v] > k) continue;
for (auto p : path[now.v])
paths.push({p.v, p.w + now.g, p.w + now.g + dis[p.v]});
}
cout << -1;//跑完之後仍找不到，則說明沒有
}
|
這道題目給了我們一個二分圖，然後希望求一個最小的點的數量，來覆蓋這一個二分圖的所有邊。我們求出最大匹配，在每個匹配的其中一個點上放置一個點即可覆蓋，因此該題實際上是求最大匹配數，我們把二分圖各邊的容量設爲1，然後加入源點s並依次連至左邊的元素，右邊的元素依次連至匯點t，該問題便轉化爲了一個網絡流問題，而且是單位容量的簡單網絡流。對於這種特殊情況的網絡流，可使用Hopcroft算法達到$O(m\sqrt n)$的複雜度，使用常規的dinic算法也可以平穩通過。以下代碼爲dinic算法（具體做法見H題）
代碼及註釋：
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
|
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
int e, c;
};
int a, b, m, cur[200002], tail = 0, depth[200002], End;
bool visited[200002];
edge edges[500000];
vector<int> paths[200002];
inline void addedge(int s, int e, int c) {
edges[tail] = {e, c};
paths[s].push_back(tail++);
edges[tail] = {s, 0};
paths[e].push_back(tail++);
}
bool dinic_bfs() {
RST(depth);
RST(visited);
*visited = 1;
queue<int> q;
q.push(0);
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto p : paths[now]) {
if (!visited[edges[p].e] && edges[p].c) {
depth[edges[p].e] = depth[now] + 1;
q.push(edges[p].e);
visited[edges[p].e] = 1;
}
}
}
return visited[End];
}
int dinic_dfs(int now, int cap) {
if (now == End || !cap) return cap;
for (auto &i = cur[now]; i < paths[now].size(); ++i) {
auto &p = paths[now][i];
if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
edges[p].c -= tmp;
edges[p ^ 1].c += tmp;
if (tmp) return tmp;
}
}
depth[now] = -1;
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> a >> b >> m;
End = a + b + 1;//0爲源點，1到a+b爲二分圖中點，a+b+1爲匯點
while (m--) {
int s, e;
cin >> s >> e;
addedge(s, e + a, 1);
}
FOR(i, 1, a + 1) addedge(0, i, 1);
FOR(i, 1, b + 1) addedge(i + a, End, 1);//建好圖，後面就搬H題過來了
int result = 0;
while (dinic_bfs()) {
RST(cur);
int tmp;
while ((tmp = dinic_dfs(0, INT_MAX >> 2))) result += tmp;
}
cout << result;
}
|
這題求的是免費K條邊的最短路。我們的一個容易想到的直觀的思路是做分層圖，把已經免費的次數作爲一個維度建圖，但是如果完整的建完整張圖，會導致內存超出，而分層圖中存在大量的重複邊，可以都從第一層取邊，然後再加上跨層的邊。但我覺得這題更好的思路是，最短路算法本質上是一個一維狀態的動態規劃（dijkstra偏向於貪心，是bfs的擴展，但其本質上仍然是動態規劃的一種），而這題我們需要的是一個二維的動態規劃。我們可以按照最短路算法思路，在其基礎上使用位置+已免費邊數的狀態替換位置狀態，在狀態轉移的過程中，由最短路算法的$dis[q]=min{dis[p]+w(p\to q)}$，拓展爲$dis[q][h]=min({dis[p][h]+w(p\to q)},{dis[p][h-1]})$，p爲所有存在邊$p\to q$的點。然後該方程的性質仍然滿足dijkstra的要求（轉移過程中$dis[q][h]$不小於$dis[p][h]$和$dis[p][h-1]$)，因此可以按照dijkstra的思路，用修改版的dijkstra求解。複雜度$O(kmlogkn)$。spfa的話，直接交貌似會TLE，SLF優化貌似對這種情況效果比較好。
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int s, t, k;
ll dis[10005][25];
struct status {//原版dijstra是位置+當前位置的最短路，這裏增加來b表示免費的次數
int a = 0, b = 0;
ll dis;
bool operator<(status x) const { return dis > x.dis; }//注意這裏dis要靜態保存，去掉dis然後動態計算(return dis[a][b] > dis[x.a][x.b])會導致順序出錯，WA on 10
};
struct edge {
int v = 0, w = 0;
};
vector<edge> path[10005];
ll dijkstra() {
RSTV(dis, 0x7f);
priority_queue<status> q;
for (auto &p : dis[s]) p = 0;
q.push({s, 0});
bool visited[10005][25];
while (!q.empty()) {
status now = q.top();
q.pop();
if (visited[now.a][now.b]) continue;
visited[now.a][now.b] = 1;
for (auto &p : path[now.a]) {
if (dis[p.v][now.b] > dis[now.a][now.b] + p.w) {
dis[p.v][now.b] = dis[now.a][now.b] + p.w;
q.push({p.v, now.b, dis[p.v][now.b]});
}//第一種轉移，同正常的dijkstra
if (now.b < k && dis[p.v][now.b + 1] > dis[now.a][now.b]) {
dis[p.v][now.b + 1] = dis[now.a][now.b];
q.push({p.v, now.b + 1, dis[p.v][now.b + 1]});
}//第二種轉移，跨層，dis值不增加
}
}
return dis[t][k];
}
signed main() {//建圖，跑最短路，輸出
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m >> k >> s >> t;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
path[u].push_back({v, w});
path[v].push_back({u, w});
}
cout << dijkstra();
}
|
這題有些複雜，購買物品需要花費，購買某個集合的所有物品可獲得相應的獎勵，答案要求是兩者差最大，而不是限制最大花費。這樣看起來比動態規劃中01揹包問題複雜得多。這種問題稱爲最大權閉合子圖問題，我們從源點連接所有的物品，所有集合連向匯點，容量均取正。然後根據包含關係，用無限容量的邊連接物品和集合。這樣一來，就可以用割去某個物品到源點的邊模擬購買此物品，某個集合被買完之後其到終點的流被切斷。這樣一來我們求一個割，即使得所有的邊都被割斷，所花費的最小代價，這樣對於每個集合，要麼獲得並且花費了相應的代價，要麼放棄了該集合。所有集合的總的壓歲錢數量減去此時的割，就是他可以剩下的壓歲錢。我們要求最大的剩餘壓歲錢，就要求最小割。顯然，我們按照最大流的路徑去割是最佳方案，這樣最小割就等於最大流（最大流做法見H題）。複雜度$O((n+m)^2\sum k)$
代碼及註釋
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
int e, c;
};
int n, m, t, depth[20002], tail = 0, cur[20002];
E edges[250000];
bool visited[20002];
vector<int> paths[20002];
inline void addedge(int s, int e, int c) {
edges[tail] = {e, c};
paths[s].push_back(tail++);
edges[tail] = {s, 0};
paths[e].push_back(tail++);
}
bool dinic_bfs() {
RST(depth);
RST(visited);
visited[0] = 1;
queue<int> q;
q.push(0);
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto p : paths[now]) {
if (!visited[edges[p].e] && edges[p].c) {
depth[edges[p].e] = depth[now] + 1;
q.push(edges[p].e);
visited[edges[p].e] = 1;
}
}
}
return visited[t];
}
int dinic_dfs(int now, int cap) {
if (now == t || !cap) return cap;
for (auto &i = cur[now]; i < paths[now].size(); ++i) {
auto &p = paths[now][i];
if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
edges[p].c -= tmp;
edges[p ^ 1].c += tmp;
if (tmp) return tmp;
}
}
depth[now] = -1;
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
FOR(i, 1, m + 1) {
int tmp;
cin >> tmp;
addedge(0, i, tmp);
}
t = m + n + 1;
int sum = 0;
FOR(i, m + 1, t) {
int c, k;
cin >> c >> k;
sum += c;//計算所有集合的壓歲錢數量總和
addedge(i, t, c);
while (k--) {
int tmp;
cin >> tmp;
addedge(tmp, i, INT_MAX >> 1);
}
}//建圖完，0爲源點，1到m爲物品，m+1到m+n爲集合，m+n+1爲匯點，然後跑最大流
int result = 0;
while (dinic_bfs()) {
RST(cur);
int tmp;
while ((tmp = dinic_dfs(0, INT_MAX >> 1))) result += tmp;
}
cout << sum - result;//輸出結果
}
|
這題是一道差分約束，某兩個量存在一個大於關係，可以用一條權值爲1（它們至少相差1）的有向邊連接（小於則相反），等於就是權值爲0的雙向邊，這樣，然後從源點向每條邊添加權值爲最小值1的邊，這樣源點到每個點的最長路長度就是它的最小值，題目要求輸出的就是這些值的和。如果有環就說明存在矛盾。帶判環的spfa可以用來解決這個問題。複雜度$O(nm)$
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
|
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
int v, l;
};
vector<edge> path[10001];
int dis[1001];
int spfa() {
RSTV(dis, 0x80);
queue<int> q;
*dis = 0;
int cnt[1001] = {0};
q.push(0);
bool has[1001] = {1};
++*cnt;
while (!q.empty()) {
int now = q.front();
q.pop();
has[now] = 0;
for (auto p : path[now])
if (dis[p.v] < dis[now] + p.l) {
dis[p.v] = dis[now] + p.l;
if (!has[p.v]) {
q.push(p.v);
has[p.v] = 1;
++cnt[p.v];
if (cnt[p.v] > 1000) return 0;
}
}
}
return 1;
}
int main() {
int n, m;
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
while (m--) {
int a, b, o;
cin >> o >> a >> b;
switch (o) {
case 1:
path[b].push_back({a, 1});
break;
case 2:
path[a].push_back({b, 1});
break;
case 3:
path[a].push_back({b, 0});
path[b].push_back({a, 0});
}
}//建圖，過程如前面的描述
FOR(i, 1, n + 1) path->push_back({i, 1});
int result = 0;
if (spfa()) {
FOR(i, 1, n + 1) result += dis[i];
cout << result;
} else//如果spfa跑失敗了就輸出-1
cout << -1;
}
|
這題，最少花費，可以讓人聯想到圖上面的最短路，而問題的關鍵就是怎麼建圖，即找到滿足要求的點（狀態）和轉移路徑。狀態的描述方式爲二進制（參考狀壓dp。然後跑dijkstra即可。（點和邊的判斷方式見註釋），複雜度貌似爲$O(2^n+2^{2(n-\overline m)}+2^{n-\overline m}C_{n-\overline m}^{k-\overline m})$，$\overline m$是$m$減去$m$對cp關係中環的數量，似乎$n$很大(15)，$m$很小(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
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
int v, l;
};
int pos = 0, n, m, k, point[2 << 16];//末位表示潔姐姐，然後從右到左依次表示其他人
vector<E> path[2 << 16];
pii against[15];
bool judge_p(int x) {//判斷點（狀態）
if ((x & 1)) return 1;//如果潔姐姐在當然沒問題
FOR(i, 0, m)
if (x >> against[i].first & 1 && x >> against[i].second & 1) return 0;//如果不在就要判斷有沒有cp，沒有才過關
return 1;
}
int judge_e(int x, int y) {//判斷邊（轉移）
int det = x ^ y, cnt = 0;
if (max(x, y) - min(x, y) != det) return 0;//去掉既有有人上，又有人下的情況
if (!(det & 1)) return 0;//去掉潔姐姐沒有參加的情況
FOR(i, 0, 16) cnt += det >> i & 1;
return cnt > k ? 0 : cnt;//參加的人不能超過k，滿足條件的輸出返回人數，作爲增加的邊的邊權。
}
void addedge(int u, int v, int l) {
path[u].push_back({v, l});
path[v].push_back({u, l});
}
int dijkstra() {
priority_queue<pii> q;
bool visited[2 << 16] = {0};
int dis[2 << 16];
RSTV(dis, 0x3f);
*dis = 0;
q.push({0, 0});
while (!q.empty()) {
pii now = q.top();
q.pop();
if (visited[now.first]) continue;
visited[now.first] = 1;
for (auto &p : path[now.first]) {
if (dis[p.v] > dis[now.first] + p.l) {
dis[p.v] = dis[now.first] + p.l;
q.push({p.v, dis[p.v]});
}
}
}
return dis[(1 << (n + 1)) - 1] == 0x3f3f3f3f ? 0 : dis[(1 << (n + 1)) - 1];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
FOR(i, 0, m) {//記錄cp關係
int u, v;
cin >> u >> v;
against[pos++] = make_pair(u, v);
}
pos = 0;
int Max = (1 << (n + 1)) - 1;
FOR(i, 0, 1 << (n + 1))
if (judge_p(i) && judge_p(Max - i)) point[pos++] = i;//必須兩邊都ok，纔可以
int tmp;
FOR(i, 0, pos)
FOR(j, i, pos)
if ((tmp = judge_e(point[i], point[j]))) addedge(point[i], point[j], tmp);//遍歷點的所有組合，判斷並添加邊
if ((tmp = dijkstra()))//跑最短路，到不了就輸出"mole"
cout << tmp;
else
cout << "mole";
}
|
這題是在三維空間上面取一棵生成樹，求這棵樹的$\frac{\sum h}{\sum d}$的最小值。我們假設這個值爲ans，則${\sum h}\geq ans\sum d$，記最小生成樹上的邊集合爲$A$，則$\sum (e.h-ans \cdot e.d)=0,e\in A$。當ans過大時，$\sum (e.h-ans \cdot e.d) < 0,e\in A$，過小則反之。這樣一來，我們就可以用二分套最小生成樹來求解。最小生成樹部分用prim跑得飛快，用kruskal要慢一些，注意常數別太差還是能過。複雜度$O(Alognz)$，$A$爲最小生成樹的複雜度
代碼及註釋：（kruskal）
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int fa[1001], depth[1001];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
u = find(u), v = find(v);
if (depth[u] > depth[v])
fa[v] = u;
else {
fa[u] = v;
if (depth[v] == depth[u]) ++depth[v];
}
}
struct E {
int u, v;
double w;
inline bool operator<(E x) const { return w < x.w; }
};
struct P {
int x, y, z;
};
P points[1001];
E edge[500001];
int pos = 0;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
FOR(i, 0, n) cin >> points[i].x >> points[i].y >> points[i].z;
double sum, ans = 10000000;
bool a = 0;
double tmp[2] = {0, 10000000};//中間開始二分
do {
ans = (tmp[0] + tmp[1]) / 2;
pos = sum = 0;
FOR(i, 0, n)
FOR(j, i + 1, n)
edge[pos++] = {i, j,
abs(points[i].z - points[j].z) -
ans * sqrt(((ll)points[i].x - points[j].x) *
(points[i].x - points[j].x) +
((ll)points[i].y - points[j].y) *
(points[i].y - points[j].y))};
for (int i = 0; i < n; ++i) fa[i] = i;//每次要重新加邊
RST(depth);
int i = 0;
sort(edge, edge + pos);
for (auto &p : edge)
if (i == n - 1)
break;
else if (find(p.u) == find(p.v))
continue;
else {
++i;
sum += p.w;
connect(p.u, p.v);
}
tmp[sum < 0] = ans;
} while (abs(tmp[0] - tmp[1]) >= 0.0001);//精度1e-4
cout << fixed << setprecision(3) << ans;
}
|