水题笔记_ APIO水题选(xiā)做 [图论, 翻车]

最近看见一个省队集训的课件…那就做一做吧…

APIO2008 免费道路

之前做过这种求有限制条件生成树的题…自己赋一下边权就好了

按照先选收费的边来生成一棵树, 这样就可以确定哪些免费边非选不可, 然后把这些边加入生成树中, 再随便挑点免费边加进去凑够$k$个, 然后再加收费边凑成生成树就好了

讲个鬼故事我一开始以为他要求一个子图, 结果他让求生成树…

所以我想裱讲课的人

...GG

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
/**************************************************************
Problem: 3624
User: Cansult
Language: C++
Result: Accepted
Time:304 ms
Memory:4540 kb
****************************************************************/

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN (200000 + 5)
#define MAXM (100000 + 5)
using namespace std;
struct edg
{
int from, to, cost, bh;
}b[MAXM];
int fa[MAXN], n, m, k;
int find(int x)
{ return (x == fa[x] ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
bool cmp1(edg x, edg y)
{ return x.cost > y.cost; }
bool cmp2(edg x, edg y)
{ return x.cost < y.cost; }
void solve()
{
vector<edg> chosen;
sort(b + 1, b + m + 1, cmp1);
for (int i = 1; i <= n; i++)
fa[i] = i;
int cntb = 0, cntk = 0;
for (int i = 1; i <= m; i++)
{
if (find(b[i].from) != find(b[i].to))
{
++cntb;
uni(b[i].from, b[i].to);
if (!b[i].cost)
chosen.push_back(b[i]);
}
if (cntb == n - 1)
break ;
}
bool vis[MAXN];
memset(vis, false, sizeof(vis));
cntb = 0;
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 0; i < chosen.size(); i++)
{
vis[chosen[i].bh] = true;
uni(chosen[i].from, chosen[i].to);
++cntk, ++cntb;
}
sort(b + 1, b + m + 1, cmp2);
for (int i = 1; i <= m; i++)
{
if (vis[b[i].bh] || (cntk >= k && (!b[i].cost)))
continue;
if (find(b[i].from) != find(b[i].to))
{
++cntb;
uni(b[i].from, b[i].to);
chosen.push_back(b[i]);
if (!b[i].cost)
++cntk;
}
if (cntb >= n - 1)
break;
}
int cntf = 0;
for (int i = 1; i <= n; i++)
if (fa[i] == i)
++cntf;
if (cntf > 1 || cntk != k || cntb != n - 1)
puts("no solution");
else
for (int i = 0; i < chosen.size(); i++)
printf("%d %d %d\n", chosen[i].from, chosen[i].to, chosen[i].cost);
}
int main(int argc, char const *argv[])
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &b[i].from, &b[i].to, &b[i].cost), b[i].bh = i;
solve();
return 0;
}

APIO2010巡逻

想到了$k = 1$的时候是找直径, 然后加在两头…

所以$k = 2$的情况就是把那个环去掉然后再找最长链(注意不是直径)…Emmmmm有趣…

所以这么把第一个环去掉呢, 考虑对答案的贡献: ans = ((n - 1) << 1) - length + 1 (在最长链上不用走过去再走回来了, 然后要多经过新加的那一条边) 这是$k = 1$的情况, 那么我们在做第二个环的时候, 把第一个环的边的边权全部赋成$-1$, 这样再减去的时候就不会对答案产生影响(即一条边减了两次)了

还有要注意的一个地方是…我写了找树的直径, 然后一直70不明觉厉…去某谷交发现有三个样例, 然后第二个就过不了…发现不能用找直径的方法做…

反例

大概找第一个环完了就是这个样子, 结果再找直径, 他不会找$6 \to 8$, 而是找了$1 \to 1$, 然后你就凉了, 这个按照高大上的舒老师说的, 要写最长链DP…

Orz

然后最长链抄的hzwer爷爷的…

注意几个问题:

  • 记得初始化(尤其maxz)
  • 在记录第二长的边的时候, 不是赋成他子节点的第二长的边的编号, 而是子节点最长的边的编号…(见line53)
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
/**************************************************************
Problem: 1912
User: Cansult
Language: C++
Result: Accepted
Time:1492 ms
Memory:8768 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000 + 5)
#define INF (0x7fffffff)
#define rev(i) ((((i) - 1) ^ 1) + 1)
#define pii pair<int, int>
using namespace std;
struct dre
{
int s, t, cost;
dre() {}
dre(int dqs, int dqt, int dqc): s(dqs), t(dqt), cost(dqc) {}
};
struct node
{
int max1, max2, max1wz, max2wz, fa;
}ta[MAXN];
struct edg
{
int from, to, next, cost;
}b[MAXN << 1];
int g[MAXN], cntb, n, k, pre[MAXN], dis[MAXN], maxz = -INF, maxs, maxt, maxr;
int dfs(int dq)
{
ta[dq].max1wz = ta[dq].max2wz = dq, ta[dq].max1 = ta[dq].max2 = 0;
for (int i = g[dq]; i; i = b[i].next)
if (ta[dq].fa != b[i].to)
{
pre[b[i].to] = i;
ta[b[i].to].fa = dq;
int dqc = b[i].cost + dfs(b[i].to);
if (dqc > ta[dq].max1)
{
ta[dq].max2 = ta[dq].max1, ta[dq].max2wz = ta[dq].max1wz;
ta[dq].max1 = dqc;
ta[dq].max1wz = ta[b[i].to].max1wz;
}
else if (dqc > ta[dq].max2)
{
ta[dq].max2 = dqc;
ta[dq].max2wz = ta[b[i].to].max1wz; // 注意这个地方可不是赋成ta[b[i].to].max2wz...
}
}
if (ta[dq].max2 + ta[dq].max1 >= maxz)
{
maxs = ta[dq].max1wz;
maxt = ta[dq].max2wz;
maxr = dq;
maxz = ta[dq].max2 + ta[dq].max1;
}
return ta[dq].max1;
}
int solve()
{
int re = ((n - 1) << 1);
if (!k)
return re;
ta[1].fa = 1;
dfs(1);
int fir = maxz;
if (k == 1)
return (re - maxz + 1);
for (int i = maxs; i != maxr; i = b[pre[i]].from)
b[pre[i]].cost = b[rev(pre[i])].cost = -1;
for (int i = maxt; i != maxr; i = b[pre[i]].from)
b[pre[i]].cost = b[rev(pre[i])].cost = -1;
for (int i = 1; i <= n; i++)
ta[i].max1 = ta[i].max2 = 0, ta[i].max1wz = ta[i].max2wz = i;
maxz = -INF;
dfs(1);
return (re - maxz + 1 - fir + 1);
}
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1, srx, sry; i < n; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry, 1), adn(sry, srx, 1);
}
printf("%d\n", solve());
return 0;
}

未完待续…

By 沙茶 Cansult