【BZOJ3362】[Usaco2004 Feb]Navigation Nightmare 导航噩梦
Description
农夫约翰有N(2≤N≤40000)个农场，标号1到N,M(2≤M≤40000)条的不同的垂直或水平的道路连结着农场，道路的长度不超过1000.这些农场的分布就像下面的地图一样，
.jpg)
图中农场用F1..F7表示, 每个农场最多能在东西南北四个方向连结4个不同的农场．此外，农场只处在道路的两端．道路不会交叉且每对农场间有且仅有一条路径．邻居鲍伯要约翰来导航，但约翰丢了农场的地图，他只得从电脑的备份中修复了．每一条道路的信息如下：
从农场1往南经距离3到达农场4
从农场1往东经距离13到达农场6
当约翰重新获得这些数据时，他有时被的鲍伯的问题打断：“农场1到农场2的曼哈顿距离是多少？”所谓在(x1，y1)和(x2，y2)之间的“曼哈顿距离”，就是lx1 - x2|+ly1 - y2|．如果已经有足够的信息，约翰就会回答这样的问题（在上例中答案是23），否则他会诚恳地抱歉并回答-1.
Input
第1行：两个分开的整数N和M.
第2到M+1行：每行包括4个分开的内容，F1，F2，L，D分别描述两个农场的编号，道路的长度，F1到F2的方向N，E，S，W．
第M+2行：一个整数，K(1≤K≤10000)，表示问题个数．
第M+3到M+K+2行：每行表示一个问题，由3部分组成：F1，F2，J．其中Fi和F2表示两个被问及的农场．而J(1≤J≤M)表示问题提出的时刻．J为1时，表示得知信息1但未得知信息2时．
Output
第1到K行：每行一个整数，回答问题．表示两个农场间的曼哈顿距离．不得而知则输出-1.
Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6
Sample Output
13
-1
10
-1
10
HINT
在时刻1，约翰知道1到6的距离为13;在时刻3，1到4的距离仍然不知道；在时刻6，位置6向北3个距离，向西7个距离于位置2，所以距离为10.
题解：BZOJ题意实在捉鸡，本人强行自编题目描述
题中由于给了所有点间有且只有一条路径，所以就是棵树，即m=n-1
然后看着像个树形DP，但是不能离线，但我们发现点和点之间的关系具有可传递性（即可加性），所以很好地符合了加权并查集的性质。那么我们只需要先按时间排序，然后用双标记的加权并查集来维护就好了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int f[40010],x[40010],dx[40010],y[40010],dy[40010],rx[40010],ry[40010],ans[40010];
char str[5];
struct QUERY
{
int qa,qb,org,tim;
}q[40010];
bool cmp(QUERY a,QUERY b)
{
return a.tim<b.tim;
}
int find(int a)
{
if(f[a]==a) return a;
int t=f[a];
f[a]=find(f[a]),dx[a]+=dx[t],dy[a]+=dy[t];
return f[a];
}
int z(int a)
{
return a>0?a:-a;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,a,b;
for(i=1;i<=m;i++)
{
scanf("%d%d%d%s",&x[i],&y[i],&a,str);
if(str[0]=='E') rx[i]=a;
if(str[0]=='W') rx[i]=-a;
if(str[0]=='N') ry[i]=a;
if(str[0]=='S') ry[i]=-a;
}
scanf("%d",&m);
for(i=1;i<=n;i++) f[i]=i;
for(i=1;i<=m;i++) scanf("%d%d%d",&q[i].qa,&q[i].qb,&q[i].tim),q[i].org=i;
sort(q+1,q+m+1,cmp);
for(i=j=1;i<=m;i++)
{
for(;j<=q[i].tim;j++)
{
a=find(x[j]),b=find(y[j]);
f[a]=b,dx[a]=rx[j]+dx[y[j]]-dx[x[j]],dy[a]=ry[j]+dy[y[j]]-dy[x[j]];
}
if(find(q[i].qa)!=find(q[i].qb)) ans[q[i].org]=-1;
else ans[q[i].org]=z(dx[q[i].qa]-dx[q[i].qb])+z(dy[q[i].qa]-dy[q[i].qb]);
}
for(i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}
【BZOJ3363】[Usaco2004 Feb]Cow Marathon 奶牛马拉松
Description
最近美国过度肥胖非常普遍，农夫约翰为了让他的奶牛多做运动，举办了奶牛马拉松．马拉松路线要尽量长，所以，告诉你农场的地图（该地图的描述与上题一致），请帮助约翰寻找两个最远农场间的距离．
Input
第1行：两个分开的整数N和M.
第2到M+1行：每行包括4个分开的内容，Fi，F2，L，D分别描述两个农场的编号，道路的长度，F1到F2的方向N，E，S，W．
Output
一个整数，表示最远两个衣场间的距离．
Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
Sample Output
52
最长的马拉松路线从2通过4，1，6，3到5；总长为：20+3+12+9+7=52
最长的马拉松路线从2通过4，1，6，3到5；总长为：20+3+12+9+7=52
题解：求树的直径：先以1为根DFS找出深度最大的点，然后再以这个点为根找出深度最大的，就是直径
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=40010;
int n,m,cnt,maxx;
int to[maxn<<1],next[maxn<<1],head[maxn],val[maxn<<1],s[maxn];
char str[5];
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x,int fa)
{
maxx=(s[maxx]<s[x])?x:maxx;
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa) s[to[i]]=s[x]+val[i],dfs(to[i],x);
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,a,b,c;
memset(head,-1,sizeof(head));
for(i=1;i<=m;i++) scanf("%d%d%d%s",&a,&b,&c,str),add(a,b,c),add(b,a,c);
dfs(1,0),s[maxx]=0,dfs(maxx,0);
printf("%d",s[maxx]);
return 0;
}
【BZOJ3364】[Usaco2004 Feb]Distance Queries 距离咨询
Description
奶牛们拒绝跑马拉松，因为她们悠闲的生活无法承受约翰选择的如此长的赛道．因此约翰决心找一条更合理的赛道，他打算咨询你．此题的地图形式与前两题相同．但读入地图之后，会有K个问题．每个问题包括2个整数，就是约翰感兴趣的2个农场的编号，请尽快算出这2个农场间的距离．
Input
第1到I+M行：与前两题相同；
第2+M行：一个整数K(1≤K≤10000)．
第3+M到2+M+K行：每行输入2个整数，代表两个农场．
Output
对每个问题，输出单独的一个整数，给出正确的距离．
Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6
Sample Output
13
3
36
农场2到农场6有20+3+13=36的距离
3
36
农场2到农场6有20+3+13=36的距离
题解：倍增LCA
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=40010;
int n,m,cnt,ans;
int to[maxn<<1],next[maxn<<1],head[maxn],val[maxn<<1],f[maxn][25],s[maxn],dep[maxn];
char str[5];
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x)
{
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=f[x][0]) f[to[i]][0]=x,dep[to[i]]=dep[x]+1,s[to[i]]=s[x]+val[i],dfs(to[i]);
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,a,b,c;
memset(head,-1,sizeof(head));
for(i=1;i<=m;i++) scanf("%d%d%d%s",&a,&b,&c,str),add(a,b,c),add(b,a,c);
dfs(1);
for(j=1;(1<<j)+1<=n;j++) for(i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
ans=s[a]+s[b];
if(dep[a]<dep[b]) swap(a,b);
for(j=20;j>=0;j--) if(dep[a]-(1<<j)>=dep[b]) a=f[a][j];
if(a==b)
{
printf("%d
",ans-2*s[a]);
continue;
}
for(j=20;j>=0;j--) if(f[a][j]!=f[b][j]) a=f[a][j],b=f[b][j];
ans-=2*s[f[a][0]];
printf("%d
",ans);
}
return 0;
}
【BZOJ3365】[Usaco2004 Feb]Distance Statistics 路程统计
Description
在得知了自己农场的完整地图后（地图形式如前三题所述），约翰又有了新的问题．他提供
一个整数K(1≤K≤109)，希望你输出有多少对农场之间的距离是不超过K的．
Input
第1到I+M行：与前三题相同；
第M+2行：一个整数K.
Output
农场之间的距离不超过K的对数．
Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
10
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
10
Sample Output
5
有五对道路之间的距离小于10
1-4,距离为3
4-7,距离为2
1-7,距离为5
3-5,距离为7
3-6,距离为9
有五对道路之间的距离小于10
1-4,距离为3
4-7,距离为2
1-7,距离为5
3-5,距离为7
3-6,距离为9
题意：同POJ1741，同BZ1468
题解：点分治，第一次写感觉自己代码常数∞∞∞
谈谈点分治吧~
我们对以x节点为根的子树进行分治，只考虑经过x的路径，然后递归计算不经过x的路径，所以现在问题是怎么求x的子树中有多少条长度≤K的路径
我们先求出x子树中所有点到x的深度dep[i]，那么我们要的就是dep[i]+dep[j]≤K的(i,j)对数，然后呢？
我们采用双指针法来实现这个过程。我们先将dep排序，用两个指针l,r从区间两边向中间平移，始终保证dep[l]+dep[r]≤K，那么(l,r]中的点到l的路径长度就都≤K，直接更新答案，单次计算时间复杂度O(nlogn)
但问题又出现了，这样计算可能导致(i,j)的路径不经过x也可能被算进去，于是我们依次算出x的儿子的子树中(i,j)的对数（此时dep[i]还是i到x的深度），然后用ans减去这些重复的对数就好了
这样，我们层层递归下去，如果给你的树比较平滑，那么总的时间复杂度应该不会太高；但假如给你的树是一条链，那么是时间复杂度直接O(n*nlogn)，连暴力都不如
于是我们不能以1为根来搞，而是要以树的重心为根（树的重心指：删去这个点后，使所有连通块的点个数的最大值最小），并且每次递归都要重新找出子树中的重心向下搜（我原来只找了整棵树的重心。。。），这样每个点至多出现在log个点的子树中，才能保证时间复杂度为O(nlogn*logn)
为什么改了那么多遍感觉常数还是std的214748647倍~~~
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=40010;
char str[5];
int n,k,cnt,root,maxx,ans,tot;
int to[maxn<<1],next[maxn<<1],head[maxn],val[maxn<<1],dep[maxn<<1],p[maxn<<1],siz[maxn],vis[maxn];
void getroot(int x,int fa)
{
int i,tmp=0;
siz[x]=1;
for(i=head[x];i!=-1;i=next[i])
{
if(to[i]==fa||vis[to[i]]) continue;
getroot(to[i],x);
siz[x]+=siz[to[i]];
tmp=max(tmp,siz[to[i]]);
}
if(max(tot-siz[x],tmp)<maxx) maxx=max(tot-siz[x],tmp),root=x;
}
void getdep(int x,int fa)
{
p[++p[0]]=dep[x];
for(int i=head[x];i!=-1;i=next[i])
{
if(to[i]==fa||vis[to[i]]) continue;
dep[to[i]]=dep[x]+val[i],getdep(to[i],x);
}
}
int solve(int x)
{
p[0]=0,getdep(x,0);
int ret=0,l=1,r=p[0];
sort(p+1,p+p[0]+1);
while(l<r)
{
while(l<r&&p[l]+p[r]>k) r--;
ret+=r-l,l++;
}
return ret;
}
void dfs(int x)
{
int i;
vis[x]=1,dep[x]=0,ans+=solve(x);
for(i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]) continue;
dep[to[i]]=val[i],ans-=solve(to[i]);
maxx=1<<30,tot=siz[to[i]],getroot(to[i],x);
dfs(root);
}
}
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
int main()
{
int i,a,b,c;
scanf("%d%d",&n,&a);
memset(head,-1,sizeof(head));
tot=n,root=1,maxx=1<<30;
for(i=1;i<n;i++)
{
scanf("%d%d%d%s",&a,&b,&c,str);
add(a,b,c),add(b,a,c);
}
scanf("%d",&k);
getroot(root,0);
dfs(root);
printf("%d
",ans);
return 0;
}