YRZ001030 @ 2020-03-02 21:38:01
两份代码一份Ac,一份Wa 我懵了 下为AC代码。 将注释地方取消注释,将53行的d[x] = ww。注释掉。 这样理论上求最短路径是一样的。但是为什么会wa呢? 求大佬告知
#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}
const int N = 30010;
int head[N],ver[N],Next[N],edge[N],tot;
int n,m,a[N];
int v[N],Size[N],ans,root;///找到树的重心
int weight[50001000];
int vis[N];
int book[N];
int d[N],b[N],point[N],top;
void add(int x,int y,int w){
ver[++ tot] = y; edge[tot] = w;
Next[tot] = head[x]; head[x] = tot;
}
void get_root(int x,int far,int n){///求子树的重心
Size[x] = 1;
int max_part = 0;
for(int i = head[x]; i; i = Next[i]){
int y = ver[i];
if(vis[y] || y == far) continue;
get_root(y,x,n);
Size[x] += Size[y];
max_part = max(max_part,Size[y]);
}
max_part = max(max_part,n - Size[x]);
if(max_part < ans || root == 0) {
ans = max_part;
root = x;
}
return ;
}
void get_dist(int x,int far,int ww,int from){
point[++ top] = x; b[x] = from;
d[x] = ww;///将这里注释
for(int i = head[x]; i; i = Next[i]){
int y = ver[i];
if(y == far || vis[y]) continue;
// d[y] = d[far] + edge[i];
get_dist(y,x,ww + edge[i],from);
}
}
int cmp(int x,int y){
return d[x] < d[y];
}
void calc(int root)
{
top = 0;
point[++ top] = root;
d[root] = 0; b[root] = root;
for(int i = head[root]; i; i = Next[i])
{
int y = ver[i];
if(vis[y]) continue;
// d[y] = edge[i];
get_dist(y,root,edge[i],y);
}
sort(point + 1,point + top + 1,cmp);
int left = 1,right = top;
for(int i = 1; i <= m; i ++){
if(book[i] == 1) continue;
left = 1; right = top;
int len = a[i];
while(left < right){
if(d[point[left]] + d[point[right]] < len) left ++;
else if(d[point[left]] + d[point[right]] > len) right --;
else if(b[point[left]] == b[point[right]]) {
if(d[point[right]] == d[point[right - 1]]) right --;
else left ++;
} else {book[i] = 1;break;}
}
}
}
void solve(int u)
{
vis[u] = 1; top = 0;
calc(u);
for(int i = head[u]; i; i = Next[i]){
int y = ver[i];
if(vis[y]) continue;
ans = n; root = 0;
get_root(y,0,Size[y]);
solve(root);
}
}
int main()
{
n = read(); m = read();
for(int i = 1; i <= n - 1; i ++){
int x,y,w;
x = read(); y = read(); w = read();
add(x,y,w); add(y,x,w);
}
for(int i = 1; i <= m; i ++)
{
a[i] = read();
if(a[i] == 0) book[i] = 1;
}
ans = n;
get_root(1,0,n);
solve(root);
for(int i = 1; i <= m; i ++)
if(book[i] == 1) printf("AYE\n");
else printf("NAY\n");
}
by wrpwrp @ 2020-03-02 22:11:48
不一样
by wrpwrp @ 2020-03-02 22:12:08
两个第一次访问的边会不一样
by wrpwrp @ 2020-03-02 22:12:39
仔细看边那个地方,有点问题
by YRZ001030 @ 2020-03-02 22:19:30
啊啊啊 是的 我就是个猪 我把那个far改成x,wa的代码就过了。不知道想的啥去了。谢谢大佬