https://vjudge.net/article/2169

Genghis Khan the Conqueror

 

题意:求出一棵生成树后要增加原图某条边的边权,有多种可能,问新的生成树的期望值。

树形dp

如果增加的边不是生成树上的边,答案显然还是生成树。

而如果是生成树上的边那就要找到一个新边连接原边两个点所在的集合。

可以树形dp对求出的生成树处理出不在生成树上的,连接两个点的不同集合的边最小值。

枚举每个点,作为生成树的根,转化为有根树。

在固定根的情况下,用一个点的子树所有点的最小返祖边(特定是直接连接到根的边)更新这个点与它父亲的dp值。

枚举完所有根之后的dp值就是完整的dp值。

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;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int par[N], rk[N];
void init(int n) {
for (int i = 0; i <= n; i++)par[i] = i, rk[i] = 0;
}
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void uni(int x, int y) {
x = find(x), y = find(y);
if (x == y)return;
if (rk[x] < rk[y])par[x] = y;
else {
par[y] = x;
if (rk[x] == rk[y])rk[x]++;
}
}
int n, m, q;
int w[3010][3010];
struct E
{
int u, v, w;
bool operator<(const E& b)const {
return w < b.w;
}
};
vector<E>es;
vector<int>G[3010];
int dp[3010][3010], inMst[3010][3010];
int dfs(int rt, int u, int _fa) {
int s = _fa == rt || _fa == -1 ? INF : w[rt][u];
for (int v : G[u]) {
if (v == _fa)continue;
int tmp = dfs(rt, v, u);
s = min(s, tmp);
dp[u][v] = dp[v][u] = min(dp[u][v], tmp);
}
return s;
}
int main() {
while (scanf("%d%d", &n, &m) == 2 && n) {
es.clear();
init(n);
for (int i = 0; i < n; i++)G[i].clear();
memset(dp, 0x3f, sizeof(dp));
memset(w, 0x3f, sizeof(w));
memset(inMst, 0, sizeof(inMst));
for (int i = 0; i < m; i++) {
int u, v, g;
scanf("%d%d%d", &u, &v, &g);
w[u][v] = w[v][u] = g;
es.push_back(E{ u,v,g });
}
int mst = 0;
sort(es.begin(), es.end());
for (E e : es) {
int u = e.u, v = e.v;
if (find(u) != find(v)) {
uni(u, v);
inMst[u][v] = inMst[v][u] = 1;
mst += e.w;
G[u].push_back(v); G[v].push_back(u);
}
}
for (int i = 0; i < n; i++)dfs(i, i, -1);
int ans = 0;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
if (!inMst[u][v])ans += mst;
else {
ans += mst - w[u][v] + min(c, dp[u][v]);
}
}
printf("%.4lf\n", 1.0*ans / q);
}
return 0;
}

 

Portal

 

题意:给定图,多次询问,问在经过边最大值为x的情况下能在几对点之间造路。

离线+并查集

询问排序,分层加边,联通的点用并查集维护,结果就是每个并查集的内部路径数。可以在合并的同时处理出来。

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;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int par[N], rk[N], cnt[N];
void init(int n) {
for (int i = 1; i <= n; i++)par[i] = i, rk[i] = 0, cnt[i] = 1;
}
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
int uni(int x, int y) {
x = find(x), y = find(y);
if (x == y)return 0;
int res = cnt[x] * cnt[y];
if (rk[x] < rk[y])par[x] = y, cnt[y] += cnt[x];
else {
par[y] = x; cnt[x] += cnt[y];
if(rk[x] == rk[y])rk[x]++;
}
return res;
}
int n, m, q;
struct E
{
int u, v, w;
bool operator<(const E& b)const {
return w < b.w;
}
};
vector<E>G[N], es;
struct Q
{
int x, id;
bool operator<(const Q& b)const {
return x < b.x;
}
}qq[N];
int ans[N];
int main() {
while (scanf("%d%d%d", &n, &m, &q) == 3) {
init(n);
for (int i = 1; i <= n; i++)G[i].clear();
es.clear();
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(E{ u,v,w });
G[v].push_back(E{ v,u,w });
es.push_back(E{ u,v,w });
}
sort(es.begin(), es.end());
for (int i = 0; i < q; i++) {
scanf("%d", &qq[i].x);
qq[i].id = i;
}
sort(qq, qq + q);
int t = 0, tmp = 0;
for (int i = 0; i < q; i++) {
while (t < m&&es[t].w <= qq[i].x) {
int u = es[t].u, v = es[t].v, w = es[t].w;
if (find(u) != find(v))tmp += uni(u, v);
t++;
}
ans[qq[i].id] = tmp;
}
for (int i = 0; i < q; i++)printf("%d\n", ans[i]);
}
return 0;
}

 

Qin Shi Huang’s National Road System

 

题意:给定图,可以免费连一条边,但是要求这条边两端点的点权和/其他边的边权和最大。

次小生成树

枚举每条边,假设连了这条边,那么如果这条边不在最小生成树上,就必须要求包含这条边的次小生成树,可以预处理出最小生成树上任意两点的路径上边的最大值,只要把枚举到的这条边先加进去,再把路径上最大的边去掉,就是次小生成树了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int par[N], rk[N];
void init(int n) {
for (int i = 1; i <= n; i++)par[i] = i, rk[i] = 0;
}
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void uni(int x, int y) {
x = find(x), y = find(y);
if (x == y)return;
if (rk[x] < rk[y])par[x] = y;
else {
par[y] = x;
if(rk[x] == rk[y])rk[x]++;
}
}
int T, n;
struct E
{
int u, v;
double w;
bool operator <(const E& b)const {
return w < b.w;
}
};
vector<E>es;
int x[N], y[N], a[N];
double dis(int i, int j) {
return sqrt(1.0*(x[i] - x[j])*(x[i] - x[j]) + 1.0*(y[i] - y[j])*(y[i] - y[j]));
}
int vis[N];
double mx[1010][1010];
vector<E>G[N];
void dfs(int u, int _fa, double W) {
for (int i = 1; i <= n; i++) {
if (vis[i]) {
mx[i][u] = mx[u][i] = max(mx[i][_fa], W);
}
}
vis[u] = 1;
for (E e : G[u]) {
if (e.v == _fa)continue;
dfs(e.v, u, e.w);
}
}
int main() {
scanf("%d", &T);
while (T--) {
es.clear();
scanf("%d", &n);
init(n);
fill(vis, vis + n + 1, 0);
memset(mx, 0, sizeof(mx));
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &x[i], &y[i], &a[i]);
G[i].clear();
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
es.push_back(E{ i,j,dis(i,j) });
}
}
sort(es.begin(), es.end());
double sum = 0;
for (E e : es) {
int u = e.u, v = e.v;
if (find(u) != find(v)) {
G[u].push_back(e);
G[v].push_back(E{ v,u,e.w });
uni(u, v);
sum += e.w;
}
}
dfs(1, 0, 0);
double ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
ans = max(ans, 1.0*(a[i] + a[j]) / (sum - mx[i][j]));
}
}
printf("%.2lf\n", ans);
}
return 0;
}

 

Code Lock

 

题意:有n个位置,每个位置可以为26个字母中一个,给出一些区间,每次操作可以选一个区间,把区间中所有位置上的值+1,如果两种情况可以通过几次操作变得相同,则算一种,问有几种不同情况。

首先要发现若没有区间可选,则共有 26n26^n 种情况;若有1个区间,则有 26n126^{n-1} 种情况,有k个不相交的区间,则有 26nk26^{n-k} 种情况;再考虑相交的区间,这里我就只会画一下了,自己模拟一下能发现是否相交并不影响答案。

但是有时候会有无效的区间:[1,3],[4,5],[1,5][1,3],[4,5],[1,5],这里 [1,5][1,5] 是没用的,不能算,为了判断是否没用,就要看是否有几个区间能合成它。用并查集判断首尾是否在同一集合。把闭区间变为左开右闭区间 (0,3],(3,5](0,3],(3,5] ,这样两个区间就有交点了,把它们合并在一起,就能把 0,50,5 合并了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e7 + 10;
const ll mod = 1000000007;
int par[N];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void init(int n) { for (int i = 0; i <= n; i++)par[i] = i; }
void uni(int x, int y) {
x = find(x), y = find(y);
if (x == y)return;
par[x] = y;
}
int n, m;
ll Pow(ll a, int b) {
ll res = 1;
while (b) {
if (b & 1)res = res * a%mod;
a = a * a%mod;
b >>= 1;
}
return res;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
init(n);
int ans = 0;
for (int i = 0; i < m; i++) {
int l, r;
scanf("%d%d", &l, &r);
l--;
if (find(l) != find(r))ans++, uni(l, r);
}
printf("%lld\n", Pow(26, n - ans));
}
return 0;
}

 

Pseudoforest

 

题意:可能有多个连通分量,求最大生成树,但是每个连通分量的生成树里允许有一个环。

还是从大到小遍历边,但是如果两端点在一个集合,仍是可能加入答案的,只要当前集合没有其他的环,所以要标记每个集合是否有环。如果两端点不在一个集合,如果连接的两个集合都有环,连上就有两个环,也不可以,所以要判断是否两个都有环。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int par[N], rk[N];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void init(int n) { for (int i = 0; i <= n; i++)par[i] = i, rk[i] = 0; }
void uni(int x, int y) {
x = find(x), y = find(y);
if (x == y)return;
if (rk[x] < rk[y])par[x] = y;
else {
par[y] = x;
if (rk[x] == rk[y])rk[x]++;
}
}
int n, m;
struct E
{
int u, v, w;
};
vector<E>es;
bool cmp(const E& a, const E& b) { return a.w > b.w; }
int cir[N];
int main() {
while (scanf("%d%d", &n, &m) == 2 && n) {
es.clear();
init(n);
fill(cir, cir + n, 0);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
es.push_back(E{ u,v,w });
}
sort(es.begin(), es.end(), cmp);
int ans = 0;
for (E e : es) {
int u = e.u, v = e.v;
u = find(u), v = find(v);
if (u == v) {
if (cir[u])continue;
ans += e.w;
cir[u] = 1;
}
else {
if (cir[u] && cir[v])continue;
uni(u, v);
ans += e.w;
if (cir[u] || cir[v])cir[find(u)] = 1;
}
}
printf("%d\n", ans);
}
return 0;
}

 

Junk-Mail Filter

 

题意:每次操作连接两个集合,或者把某个点单独成为一个集合,问最终有几个集合。

要从并查集中删除点。

对每个点设置一个真实标记,初始时每个点就是它自己,如果要独立它,就再新建一个点,把要独立的点的真实标记指向新点,这样以后的操作都只会在新点上进行。

要注意的是,如果恰好删除了并查集的根,那么如果最后还用每个点的根是否为他自己来数个数就会少,所以要访问每个点的根,判断是否vis过。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e7 + 10;
const ll mod = 1000000007;
int par[N], rk[N];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void init(int n) { for (int i = 0; i <= n; i++)par[i] = i, rk[i] = 0; }
void uni(int x, int y) {
x = find(x), y = find(y);
if (x == y)return;
if (rk[x] < rk[y])par[x] = y;
else {
par[y] = x;
if (rk[x] == rk[y])rk[x]++;
}
}
int n, m;
int p[N], vis[N];
int main() {
int tt = 0;
while (scanf("%d%d", &n, &m) == 2 && n) {
init(n);
for (int i = 0; i < n; i++) p[i] = i;
int tot = n;
for (int i = 0; i < m; i++) {
char op; int x, y;
scanf(" %c", &op);
if (op == 'M') {
scanf("%d%d", &x, &y);
uni(p[x], p[y]);
}
else {
scanf("%d", &x);
p[x] = tot++;
par[p[x]] = p[x];
}
}
int ans = 0, tmp;
fill(vis, vis + tot, 0);
for (int i = 0; i < n; i++) {
if (!vis[tmp = find(p[i])])ans++, vis[tmp] = 1;
}
printf("Case #%d: %d\n", ++tt, ans);
}
return 0;
}

 

Zjnu Stadium

 

题意:有300列座位,每列有无限个座位,某些给出人之间隔了几列,问给出的数据有多少是错的。

带权并查集

已知A在B右边k列,就可以记为A=B+k,并查集维护每个点到根的距离,合并时要关注两个根之间的关系,在本题中就是d[f1] = z + d[y] - d[x],一维直线上画一下图就能得到。

路径压缩的时候也要注意先处理父节点,再加上父节点到根的距离,就是自己到根的距离。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int par[N], d[N];
void init(int n) {
for (int i = 0; i <= n; i++)par[i] = i, d[i] = 0;
}
int find(int x){
if (par[x] == x)return x;
int fa = par[x];
par[x] = find(par[x]);
d[x] += d[fa];
return par[x];
}
void uni(int x, int y, int f1, int f2, int z) {
par[f1] = f2;
d[f1] = z + d[y] - d[x];
}
int query(int x) {
if (par[x] == x)return d[x];
return d[x] + query(par[x]);
}
int n, m;
int main(){
while (scanf("%d%d", &n, &m) == 2) {
init(n);
int ans = 0;
while (m--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
int f1 = find(x), f2 = find(y);
if (f1 == f2) {
if (d[x] - d[y] != z)ans++;
}
else {
uni(x, y, f1, f2, z);
}
}
printf("%d\n", ans);
}
return 0;
}

 

How Many Answers Are Wrong

 

题意:给出一个区间的长度 N,及 M 个子区间和, 形如:x y z, 表示
子区间 [x, y] 的和为 z
如果一个“子区间和”与前面的“子区间和”冲突,即为错误(而且这个“子区间和”将在接下来的判断中被忽略)。
求总错误个数。

并查集+区间处理

一个大区间可以由几个不相交的小区间拼成,但是要用并查集就必须要有交点,所以又出现了,把闭区间变为左开右闭区间。

然后就当成前缀和处理,把每个前缀和作为点,又变成了给定的信息是A=B+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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int par[N]; ll d[N];
void init(int n) {
for (int i = 0; i <= n; i++)par[i] = i, d[i] = 0;
}
int find(int x){
if (par[x] == x)return x;
int fa = par[x];
par[x] = find(par[x]);
d[x] += d[fa];
return par[x];
}
void uni(int x, int y, int f1, int f2, ll z) {
par[f1] = f2;
d[f1] = z + d[y] - d[x];
}
int n, m;
int main(){
while (scanf("%d%d", &n, &m) == 2) {
init(n);
int ans = 0;
while (m--) {
int x, y; ll z;
scanf("%d%d%lld", &x, &y, &z);
x--;
int f1 = find(x), f2 = find(y);
if (f1 == f2) {
if (d[x] - d[y] != z)ans++;
}
else {
uni(x, y, f1, f2, z);
}
}
printf("%d\n", ans);
}
return 0;
}

 

Exclusive-OR

 

题意:

存在一个不会变化的,未知的长度为 n 的数列 x, 每个数都不超过 2^20, 有 3 种操作:

  1. I p v 告诉你某个元素 x[p] 的值为 v
  2. I p q v 告诉你某个元素 x[p] 和另一个元素 x[q] 的异或值 v(即 x[p] xor x[q] = v)
  3. Q k p1 p2 ...pk 查询 k 个元素的异或值(即 x[p1] xor x[p2] xor ... xor x[pk]), k 不超过 15

对于每次询问,给出答案或根据已知信息无法判断。对于每次信息,判断是否与之前矛盾。

 

并查集维护每点与根的异或值,对于每次询问,只有每个集合被查询了偶数次,根才能被抵消,否则无法判断,易证也确实无法判断。

对于每个信息,第二种就直接合并,对于第一种,要设定一个虚拟点,它的值为0,任何值与他异或都为本身,且合并时它一定要作为根。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int n, m;
char s[N];
int par[N], c[N];
int k, q[N], vis[N];
void ini(int n) { for (int i = 0; i <= n; i++)par[i] = i, c[i] = 0, vis[i] = 0; }
int find(int x) {
if (par[x] == x)return x;
int fa = par[x];
par[x] = find(par[x]);
c[x] ^= c[fa];
return par[x];
}
bool uni(int x, int y, int z) {
int f1 = find(x), f2 = find(y);
if (f1 == f2) {
if ((c[x] ^ c[y]) != z)return false;
}
if (f1 == n)swap(f1, f2); //x已赋值,y未赋值,且x^y=z
par[f1] = f2;
c[f1] = c[x] ^ c[y] ^ z;
return true;
}
int query() {
int ans = 0;
fill(vis, vis + 20, 0);
for (int i = 0; i < k; i++) {
int rt = find(q[i]);
ans ^= c[q[i]];
if (vis[i])continue;
int cnt = 0;
for (int j = i; j < k; j++) {
if (find(q[j]) == rt) {
cnt++;
vis[j] = 1;
}
}
if (rt != n && (cnt & 1))return -1;
}
return ans;
}
int main() {
int tt = 0;
while (scanf("%d%d", &n, &m) == 2 && n) {
ini(n);
printf("Case %d:\n", ++tt);
int clk = 0, flg = 1;
while (m--) {
if (!flg) { gets(s); continue; }
char op;
scanf(" %c", &op);
if (op == 'I') {
clk++;
getchar();
gets(s);
int cnt = 0, u, v = n, x;
for (int i = 0; s[i]; i++)if (s[i] == ' ')cnt++;
if (cnt == 1) {
sscanf(s, "%d%d", &u, &x);
}
else {
sscanf(s, "%d%d%d", &u, &v, &x);
}
if (!uni(u, v, x))printf("The first %d facts are conflicting.\n", clk), flg = 0;
}
else {
scanf("%d", &k);
for (int i = 0; i < k; i++)scanf("%d", &q[i]);
int ans = query();
if (ans == -1)puts("I don't know.");
else printf("%d\n", ans);
}
}
puts("");
}
return 0;
}

 

Transfer water

 

题意:有n个村庄,给定了三维坐标,每个村庄可以自己打井或者引水线,问全部有水的最小花费。

设置虚拟点作为打井,再按题意连边,就是个最小树形图模板题。

求最小树形图的朱刘算法:根据DAG图求最小树形图是对每个点选取边权最小的入边这一贪心做法,再不断把环缩点,变成DAG,同时修改边权为原边权-出点所在环内该点的出边边权,再应用贪心,直到无环。

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;
#define ll long long
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
struct E
{
int u, v, w;
}es[M];
int n, m, rt, mn[N], fa[N], tp[N], lp[N];
int zl(int n, int rt) {
int ans = 0, tot = 0;
while (1) {
for (int i = 1; i <= n; i++)mn[i] = INF, fa[i] = tp[i] = lp[i] = 0;
for (int i = 1, v, w; i <= m; i++)
if (es[i].u != es[i].v && (w = es[i].w) < mn[v = es[i].v])
mn[v] = w, fa[v] = es[i].u;
mn[rt] = 0;
for (int u = 1; u <= n; u++) {
ans += mn[u];
if (mn[u] == INF)return -1;
}
for (int u = 1, v = 1; u <= n; u++, v = u) {
while (v != rt && tp[v] != u && !lp[v])tp[v] = u, v = fa[v];
if (v != rt && !lp[v]) {
lp[v] = ++tot;
for (int k = fa[v]; k != v; k = fa[k])lp[k] = tot;
}
}
if (!tot)return ans;
for (int i = 1; i <= n; i++)if (!lp[i])lp[i] = ++tot;
for (int i = 1; i <= m; i++)
es[i].w -= mn[es[i].v], es[i].u = lp[es[i].u], es[i].v = lp[es[i].v];
n = tot, rt = lp[rt], tot = 0;
}
}
int X, Y, Z;
int a[N], b[N], c[N];
int dis(int i, int j) {
return abs(a[i] - a[j]) + abs(b[i] - b[j]) + abs(c[i] - c[j]);
}
int main() {
while (scanf("%d%d%d%d", &n, &X, &Y, &Z) == 4 && n) {
rt = n + 1, m = 0;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &a[i], &b[i], &c[i]);
es[++m] = E{ rt,i,X*c[i] };
}
for (int i = 1; i <= n; i++) {
int k;
scanf("%d", &k);
for (int j = 1; j <= k; j++) {
int v;
scanf("%d", &v);
es[++m] = E{ i,v,dis(i,v)*Y + (c[v] > c[i] ? Z : 0) };
}
}
int ans = zl(n + 1, n + 1);
if (ans == -1)puts("poor XiaoA");
else printf("%d\n", ans);
}
return 0;
}

 

Dig The Wells

 

题意:共有n个点,有k个关键点必须要有水,给出了每个点打井的花费,以及m条有向边,代表拉水线的花费,问最小花费。

与上题一样,要打井,所以建虚拟点连所有点。

之后就是一个要求k个关键点必须联通的斯坦纳树模板题。

斯坦纳树:dp[s][i]dp[s][i] 代表与 ii 的联通情况为 ss,(也有说法是以 ii 为根,且联通情况为 ss,但我认为前者更容易理解)。

分两步转移:

  1. 点内部转移。枚举 ss 的子集 ttdp[s][i]=min(dp[s][i],dp[t][i]+dp[st][i])dp[s][i] = min(dp[s][i], dp[t][i] + dp[s\bigoplus t][i])
  2. 点之间转移。dp[s][i]=min(dp[s][i],dp[s][j]+w[i][j])dp[s][i]=min(dp[s][i],dp[s][j]+w[i][j])

第二个转移看上去就和求最短路一样,所以可以用SPFA求,因为此时的 ss 都是一样的,直接把 dp[s]dp[s] 作为距离数组,把非无穷远的点作为图上的点,最小化即可。

本题有重边!!尼玛调了半天。

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<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e3 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int k, n, m;
int dp[1 << 6][N], w[N][N], c[N];
vector<int>G[N];
queue<int>q;
int inq[N];
void spfa(int* dis) {
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = 0;
for (int v : G[u]) {
if (dis[v] > dis[u] + w[u][v]) {
dis[v] = dis[u] + w[u][v];
if (!inq[v]) {
inq[v] = 1;
q.push(v);
}
}
}
}
}
int main() {
while (scanf("%d%d%d", &k, &n, &m) == 3) {
while (!q.empty())q.pop();
memset(inq, 0, sizeof(inq));
memset(dp, 0x3f, sizeof(dp));
memset(w, 0x3f, sizeof(w));
n += k;
G[0].clear();
for (int i = 1; i <= n; i++) {
G[i].clear();
scanf("%d", &w[0][i]);
w[i][0] = w[0][i];
G[0].push_back(i), G[i].push_back(0);
}
for (int i = 0; i < m; i++) {
int u, v, t;
scanf("%d%d%d", &u, &v, &t);
w[u][v] = w[v][u] = min(w[u][v], t);
G[u].push_back(v);
G[v].push_back(u);
}
n++;
for (int i = 0; i <= k; i++)dp[1 << i][i] = 0;
for (int s = 1; s < (1 << (k + 1)); s++) {
for (int i = 0; i < n; i++) {
for (int t = (s - 1)&s; t; t = (t - 1)&s)
dp[s][i] = min(dp[s][i], dp[t][i] + dp[s^t][i]);
if (dp[s][i] != INF)q.push(i), inq[i] = 1;
}
spfa(dp[s]);
}
printf("%d\n", dp[(1 << (k + 1)) - 1][0]);
}
return 0;
}

 

Peach Blossom Spring

 

题意:有k个1类点,k个2类点,要求每个1类点与1个2类点联通,且一一对应。

还是k关键点的生成树问题,但是本题并不需要所有1类点联通,而是允许一个森林,其中所有树都满足1类与2类一一对应。

那么只要一棵树里有相同数量的1类和2类点即可。

先求出2k个关键点的斯坦纳树,再试图把答案拆成几棵树,判断如果一棵树里的情况满足以上条件,就更新答案。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e3 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int T;
int n, m, k, K;
struct E
{
int v, w;
};
vector<E>G[N];
int f[1 << 10][60], dp[1 << 10];
queue<int>q; int inq[N];
void spfa(int* dis) {
while (!q.empty()) {
int u = q.front(); q.pop();
for (E e:G[u]) {
int v = e.v, w = e.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!inq[v]) {
q.push(v);
inq[v] = 1;
}
}
}
inq[u] = 0;
}
}
bool check(int s) {
int cnt = 0;
for (int i = 0; i < K; i++) {
if (s&(1 << i)) {
if (i < k)cnt++;
else cnt--;
}
}
return cnt == 0;
}
int main() {
cin >> T;
while (T--) {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; i++)G[i].clear();
memset(f, 0x3f, sizeof(f));
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
u--, v--;
G[u].push_back(E{ v,w });
G[v].push_back(E{ u,w });
}
K = 2 * k;
for (int i = 0; i < k; i++) {
f[(1 << i)][i] = 0; f[1 << (K - i - 1)][n - i - 1] = 0;
}
for (int s = 1; s < (1 << K); s++) {
for (int i = 0; i < n; i++) {
for (int t = s & (s - 1); t; t = (t - 1)&s) {
f[s][i] = min(f[s][i], f[t][i] + f[s - t][i]);
}
if (f[s][i] != INF)q.push(i), inq[i] = 1;
}
spfa(f[s]);
}
for (int sta = 1; sta < (1 << K); sta++) {
for (int i = 0; i < n; i++)
dp[sta] = min(dp[sta], f[sta][i]);
}
for (int sta = 1; sta < (1 << K); sta++)
if (check(sta))
for (int s = sta & (sta - 1); s; s = sta & (s - 1))
if (check(s)) dp[sta] = min(dp[sta], dp[s] + dp[sta - s]);
if (dp[(1 << K) - 1] == INF)puts("No solution");
else printf("%d\n", dp[(1 << K) - 1]);
}
return 0;
}

 

Interviewe

 

题意:共 nn 个人,分成 mm 块,每块 nm\lfloor \frac{n}{m} \rfloor 个人,后面的不要,每块取最大值,要求总和大于 ss,问 mm 最小值。

分块+倍增RMQ

首先枚举分成 11n\sqrt n 组,期间若有满足条件的,直接输出。

以上已经枚举完了每组为 nnn\sqrt n 的情况,还剩下每组为 11n\sqrt n 的情况,直接枚举每组人数。但是要注意对于每组为 kk 的情况,组数 mm 可能有多值,例如:共12人,分5组和分6组,每组都是2人。所以在枚举每组为2人的情况时,如果分5组就能解决问题,就不要再看分6组的了,12个人中后面的2个就不要了。

而本题相对直接枚举m的优化就在于第2步,在每组人数相同的情况下把多种组数和最多组数一起check了,12个人如果分6组不行,分5组更加不行,不需要每次都重新 O(n)O(n) check了。

总复杂度为 O(nlogn)O(n\log n)

有些题解说可以二分组数,这是错的,以下为例子。

6 4
0 0 2 3 0 0

还有的直接m从1枚举到 min(n,s/mx)min(n,s/mx),这复杂度也是不够的,比如以下。

200000 200000

1 1 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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, s;
int mx[N][25];
void ini(int n) {
for (int i = 1; i < 25; i++) { //1e7
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
}
}
}
int rmq(int a, int b) {
int len = log2(b - a + 1);
return max(mx[a][len], mx[b - (1 << len) + 1][len]);
}
int check(int k) {
int sum = 0, cnt = 0;
for (int i = 1; i + k - 1 <= n; i += k) {
cnt++;
sum += rmq(i, i + k - 1);
if (sum > s)return cnt;
}
return -1;
}
int main() {
while (scanf("%d%d", &n, &s) == 2 && n > 0) {
for (int i = 1; i <= n; i++)scanf("%d", &mx[i][0]);
int ans = -1;
ini(n);
for (int i = 1; i <= sqrt(1.0*n); i++) {
ans = check(n / i);
if (ans != -1)break;
}
if (ans == -1) {
for (int i = sqrt(1.0*n); i >= 1; i--) {
ans = check(i);
if (ans != -1)break;
}
}
printf("%d\n", ans);
}
return 0;
}