[BZOJ1912][Apio2010]patrol 巡逻
试题描述
输入
第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行，每行两个整数 a, b， 表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。
输出
输出一个整数，表示新建了K 条道路后能达到的最小巡逻距离。
输入示例
8 1 1 2 3 1 3 4 5 3 7 5 8 5 5 6
输出示例
11
数据规模及约定
10%的数据中，n ≤ 1000, K = 1；
30%的数据中，K = 1；
80%的数据中，每个村庄相邻的村庄数不超过 25；
90%的数据中，每个村庄相邻的村庄数不超过 150；
100%的数据中，3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。
题解
已经没有心情写题解了。。。又WA又T最后终于照着标程写A了
先找树的直径标上-1，再找一遍权值最大链。
我本来的想法是找两条不相交的总长度最长的链，想法应该没问题但不知为何写T了。。。先贴一发T的代码，有神犇查出错误请在评论里吐槽。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *tail;
inline char Getchar() {
if(Head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 100010
#define maxm 200010
int n, K, m, head[maxn], next[maxm], to[maxm];
void AddEdge(int a, int b) {
to[++m] = b; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; next[m] = head[a]; head[a] = m;
return ;
}
int fa[maxn], Q[maxn], hd, tl;
bool vis[maxn];
int BFS(int s) {
hd = tl = 0; Q[++tl] = s; vis[s] = 1;
while(hd < tl) {
int u = Q[++hd];
for(int e = head[u]; e; e = next[e]) if(!vis[to[e]])
fa[to[e]] = u, vis[to[e]] = 1, Q[++tl] = to[e];
}
return Q[hd];
}
bool vis2[maxn];
int pt[maxn];
int BFS2(int s) {
hd = tl = 0; Q[++tl] = s;
memset(vis2, 0, sizeof(vis2)); vis2[s] = 1;
memset(pt, 0, sizeof(pt)); pt[s] = 0;
while(hd < tl) {
int u = Q[++hd];
for(int e = head[u]; e; e = next[e]) if(!vis2[to[e]] && !vis[to[e]])
vis2[to[e]] = 1, pt[to[e]] = pt[u] + 1, Q[++tl] = to[e];
}
return Q[hd];
}
bool cmp(int a, int b){ return a > b; }
int cnt, line[maxn], mx[maxn], mx2[maxn], c2, A[maxn];
int main() {
scanf("%d%d", &n, &K);
for(int i = 1; i < n; i++) {
int a, b; scanf("%d%d", &a, &b);
AddEdge(a, b);
}
int x = BFS(1);
memset(vis, 0, sizeof(vis));
int y = BFS(x);
memset(vis, 0, sizeof(vis));
for(int u = y; u != x; u = fa[u]) vis[u] = 1, line[++cnt] = u;
vis[x] = 1; line[++cnt] = x;
if(K == 1){ printf("%d
", 2 * (n - 1) - cnt + 2); return 0; }
int ans = cnt - 1;
for(int i = 1; i <= cnt; i++) {
int u = line[i];
c2 = 0;
for(int e = head[u]; e; e = next[e]) if(!vis[to[e]]) {
x = BFS2(to[e]); A[++c2] = pt[x] + 1;
y = BFS2(x); ans = max(ans, cnt - 1 + pt[y]);
}
if(c2) {
sort(A + 1, A + c2 + 1, cmp);
if(c2 > 1) ans = max(ans, A[1] + A[2] + cnt - 1);
else ans = max(ans, A[1] + cnt - 1);
mx[i] = A[1];
}
else mx[i] = 0;
}
for(int i = 1; i <= cnt; i++) mx2[i] = max(mx[i] + i - 1, mx2[i-1]);
int _mx = 0;
for(int i = cnt; i > 1; i--) {
_mx = max(_mx, mx[i] + cnt - i);
ans = max(ans, _mx + mx2[i-1]);
}
printf("%d
", 2 * (n - 1) - ans + 2);
return 0;
}
接下来是AC代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *tail;
inline char Getchar() {
if(Head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 100010
#define maxm 200010
int n, m, head[maxn], next[maxm], to[maxm], dist[maxm];
void AddEdge(int a, int b, int c) {
to[m] = b; dist[m] = c; next[m] = head[a]; head[a] = m++;
swap(a, b);
to[m] = b; dist[m] = c; next[m] = head[a]; head[a] = m++;
return ;
}
int dia, mx, t1[maxn], t2[maxn];
int dfs(int u, int fa) {
int m1 = 0, m2 = 0;
for(int e = head[u]; e != -1; e = next[e]) if(to[e] != fa) {
int t = dfs(to[e], u) + dist[e];
if(t > m1) m2 = m1, m1 = t, t2[u] = t1[u], t1[u] = e;
else if(t > m2) m2 = t, t2[u] = e;
}
if(dia < m1 + m2) dia = m1 + m2, mx = u;
return m1;
}
int main() {
n = read(); int K = read();
memset(head, -1, sizeof(head));
memset(t1, -1, sizeof(t1));
memset(t2, -1, sizeof(t2));
for(int i = 1; i < n; i++) {
int a = read(), b = read();
AddEdge(a, b, 1);
}
dia = 0; dfs(1, 0);
int ToT = 2 * (n - 1);
ToT -= dia - 1;
if(K == 1){ printf("%d
", ToT); return 0; }
for(int e = t1[mx]; e != -1; e = t1[to[e]]) dist[e] = dist[e^1] = -1;
for(int e = t2[mx]; e != -1; e = t1[to[e]]) dist[e] = dist[e^1] = -1;
dia = 0; dfs(1, 0);
ToT -= dia - 1;
printf("%d
", ToT);
return 0;
}