https://atcoder.jp/contests/abc308/tasks
Ex - Make Q
简单无向图, N点,M边, 初始边白色, 如果要把边染色成黑色代价Ci
也就是 要 给一个环上色，且延伸一个 环内点-环外点的边，也就是视觉意义上的Q
问 画出Q的最小代价
n300
ci 1e5
4s
1024mb
我的思路
这个n300 不知道怎么用，看起来像是n^3 一类的玩意
如果给定了圆，那么延伸边，可以直接暴力枚举O(n^2)？
一个思路是最小生成树，而和最小生成树不同的是，当有同并查集的时候 直接触发 找环
问题是，每边尽量短并不意味环更短，10个1 > 3个2
钦定 环上延伸边的点
环上延伸边的点是u, 然后找环，再定延伸边
for u (O(n)): 找环?, 延伸边:O(n)
如果先定延伸边，那么就是 求不含延伸点，含固定点的最小环
似乎并不会找 含 固定点的最小环
另外，如果再处理一下， 先找含固定点的最小环，那么未包含的点就可以作为延伸点，包含的点再考虑
1
2
3
4
5
6
| 1-(1)-2-(1)-3
1-(1)-4-(1)-3
1-(3)-3
1-(100)-5
显然 最小环是 1-2-3-4-1, 长度是4,但是延伸点会是1-5长度100
而 1-2-3-1 环更大是5，可以选延伸边1-4长度1
|
题解
这样的话 for a
对于给定a
yukicokder No.1320, 找包含点a的环的时间复杂度是O(N^2)
方法:
首先以a为根建立 最短距离树
L[u] = u向上的祖先除了a深度最低的节点, L[a] = a
对于所有边 L[e[i].u] != L[e[i].v], 相当于有环 a-L[e[i].u]-...-e[i].u-e[i].v-...-L[e[i].v]-a
// 我也这样想了，没想到总的只用建立1个树，而是想成从a每条边延伸建1个树，
而这里还出了一个性质
如果 d不是b,c也是环上点那么 该方案一定不会产生贡献
1
2
3
4
5
6
7
| b-a-c
|
d 如果在环上
当前贡献 = 含a最小环 + (a-d)
而 环 a-b-..-d-a + (a-c) < 这种方案
|
因此 ans = min(图形Q) = min(图形环+一条边环上点的额外延伸边（没有非环上点的性质）) !!!!!!!!
所以这样的话，只要不是b和c就可以了！！
这样的话，那么只需要再考虑 额外边是a-b,和额外边是a-c的两种情况！！！！
代码
https://atcoder.jp/contests/abc308/submissions/43439486
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
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
int read(){int r;scanf("%d",&r);return r;}
const int inf = 1e8;
pair<int, vector<int>> shortest_cycle(const vector<vector<int>> &G, int r) {
int n = G.size();
vector<int> dist(n, 2 * inf), p(n, -1), g(n);
vector<bool> seen(n);
dist[r] = 0;
g[r] = r;
rep(_,0,n){
int mn = 2*inf, pos = -1;
rep(i,0,n) if (!seen[i] and dist[i] < mn) {
mn = dist[i];
pos = i;
}
assert(pos != -1);
seen[pos] = true;
rep(i,0,n) if (dist[i] > dist[pos] + G[pos][i]) {
dist[i] = dist[pos] + G[pos][i];
p[i] = pos;
g[i] = (pos == r ? i : g[pos]);
}
}
array<int,3> mnij = {5*inf,-1,-1};
rep(i,0,n) rep(j,i+1,n){
if (p[i] == j or p[j] == i) continue;
if (g[i] == g[j]) continue;
mnij = min(mnij, {dist[i] + dist[j] + G[i][j],i,j});
}
vector<int> res;
auto [len,a,b] = mnij;
for(;a != r;a=p[a]) res.push_back(a);
res.push_back(a);
reverse(res.begin(), res.end());
for(;b != r;b=p[b]) res.push_back(b);
return {len, res};
}
int main() {
int n=read();
int m=read();
vector G(n, vector<int>(n, inf));
rep(i,0,m){
int a=read()-1;
int b=read()-1;
int c=read();
G[a][b] = G[b][a] = c;
}
int ans = inf;
rep(a,0,n) {
auto [len, cycle] = shortest_cycle(G, a);
assert(int(cycle.size()) >= 3 and cycle[0] == a);
vector<int> adj = {cycle[1], cycle.back()};
rep(i,0,n) if(!(i == a or i == adj[0] or i == adj[1])) ans = min(ans, len + G[a][i]);
for(auto d:adj){
int ori = G[a][d];
G[a][d] = G[d][a] = inf;
ans = min(ans, shortest_cycle(G, a).first + ori);
G[a][d] = G[d][a] = ori;
}
}
printf("%d\n",ans == inf ? -1 : ans);
return 0;
}
|
总结
Ex
学习了，如何在给定图中找包含点A的最小环
虽然想到了固定 特殊点，但是没相出这个 额外引入不是Q但是不影响结果的性质
参考
官方题解