两份代码,除了求两行不同其他地方一样的

P3806 【模板】点分治 1

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的代码就过了。不知道想的啥去了。谢谢大佬


|