「BZOJ1912」[Apio2010] patrol 巡逻
Description
Input
第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行，每行两个整数 a, b， 表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。
Output
输出一个整数，表示新建了K 条道路后能达到的最小巡逻距离。
Sample Input
8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6
1 2
3 1
3 4
5 3
7 5
8 5
5 6
Sample Output
11
HINT
10%的数据中，n ≤ 1000, K = 1；
30%的数据中，K = 1；
80%的数据中，每个村庄相邻的村庄数不超过 25；
90%的数据中，每个村庄相邻的村庄数不超过 150；
100%的数据中，3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。
题解
这种题都wa了好几发觉得生活失去了希望
k=1，很显然最优的方法就是在树的直径x到y之间连一条边，这样x到y之间的距离缩短为1，答案为2(n−1)−len1+1
k=2，将树的直径上的所有边权全部标为-1，再求一次直径len2，答案为2(n−1)−len1+1−len2+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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int mx,n,K,tot,cnt=1,dia; int last[100005]; int s1[100005],s2[100005]; struct edge{ int to,next,v; }e[200005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=1; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=1; } int dfs(int x,int fa) { int mx1=0,mx2=0; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { int v=e[i].v+dfs(e[i].to,x); if(v>mx1)mx2=mx1,mx1=v,s2[x]=s1[x],s1[x]=i; else if(v>mx2)mx2=v,s2[x]=i; } if(mx1+mx2>dia)dia=mx1+mx2,mx=x; return mx1; } int main() { n=read();K=read();tot=2*(n-1); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); } dfs(1,0);tot=tot-dia+1; if(K==2) { dia=0; for(int i=s1[mx];i;i=s1[e[i].to])e[i].v=e[i^1].v=-1; for(int i=s2[mx];i;i=s1[e[i].to])e[i].v=e[i^1].v=-1; dfs(1,0);tot=tot-dia+1; } printf("%d\n",tot); return 0; } |
Subscribe
计数器 9786050
OI 课件=>
OI 课件=>