P2416 泡芙,该了一天了,求助
  • 板块题目总版
  • 楼主Elaina_
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/19 19:39
  • 上次更新2023/10/27 06:52:35
查看原帖
P2416 泡芙,该了一天了,求助
770640
Elaina_楼主2022/10/19 19:39
#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int F=700000;

int n,m,tot=1,totc,num,dcc,ro,t;
int head[F],ver[F],nxt[F],a1[F],b1[F],c1[F];
int hc[F],vc[F],nc[F];
int low[F],dfn[F],c[F];
int v[F],bri[F],vi[F],dist[F],d[F],vie[F],f[F][20],dis[F],wi[F];
int vis[F];
queue<int> q;

void add(int x,int y){
  ver[++tot]=y;
  nxt[tot]=head[x];
  head[x]=tot;
}

void tarjan(int x,int z){
  dfn[x]=low[x]=++num;
  for(int i=head[x];i;i=nxt[i]){
    int y=ver[i];
    if(!dfn[y]){
      tarjan(y,i);
      low[x]=min(low[x],low[y]);
      if(low[y]>dfn[x])
        bri[i]=bri[i^1]=1;
    }
    else if(i!=(z^1))
      low[x]=min(low[x],dfn[y]);
  }
}

void dfs(int x){
  c[x]=dcc;
  for(int i=head[x];i;i=nxt[i]){
    int y=ver[i];
    if(c[y]||bri[i])
      continue;
    dfs(y);
  }
}

void dfs1(int x,int fa){
  f[x][0]=fa;
  d[x]=d[fa]+1;
  for(int i=head[x];i;i=nxt[i]){
    int y=ver[i];
    if(y==fa)
      continue;
    wi[y]=wi[x]+vi[i];
    dis[y]=dis[x]+vie[y];
    dfs1(y,x);
  }
}

int lca(int x,int y){
  if(d[x]>d[y])
    swap(x,y);
  for(int i=t;i>=0;i--)
    if(d[f[y][i]]>=d[x])
      y=f[y][i];
  if(x==y)
    return x;
  for(int i=t;i>=0;i--)
    if(f[y][i]!=f[x][i]){
      y=f[y][i];
      x=f[x][i];
    }
  return f[x][0];
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++){
    scanf("%d%d%d",&a1[i],&b1[i],&c1[i]);
    if(a1[i]==b1[i])
      continue;
    add(a1[i],b1[i]);
    add(b1[i],a1[i]);
  }
  tarjan(1,0);
  // for(int i=2;i<=tot;i++) cout<<bri[i]<<" ";
  t=log(n)/log(2)+1;
  for(int i=1;i<=n;i++)
    if(!c[i]){
      ++dcc;
      dfs(i);
    }
  memset(head,0,sizeof(head));
  memset(ver,0,sizeof(ver));
  memset(nxt,0,sizeof(nxt));
  tot=0;
  for(int i=1;i<=m;i++){
    int x=a1[i],y=b1[i];
    if(x==y)
      continue;
    if(c[x]!=c[y]){
      add(c[x],c[y]);
      add(c[y],c[x]);
      if(c1[i]==1){
        int uo=tot-1;
        vi[tot]=1;
        vi[uo]=1;
      }
      continue;
    }
    if(c[x]==c[y]){
      if(c1[i]==1)
        vie[c[x]]=1;
      continue;
    }
  }
  dfs1(1,0);
  for(int i=1;i<=t;i++){
    for(int j=1;j<=dcc;j++){
      f[j][i]=f[f[j][i-1]][i-1];
    }
  }
  // cout<<dcc;
  // for(int i=1;i<=n;i++) cout<<c[i]<<" ";

  // for(int i=1;i<=dcc;i++) cout<<vie[i]<<" ";
  // cout<<endl;

  // for(int i=1;i<=tot;i++) cout<<vi[i]<<" ";
  // cout<<endl;

  // for(int i=1;i<=dcc;i++) cout<<dis[i]<<" ";
  // cout<<endl;

  // for(int i=1;i<=dcc;i++) cout<<wi[i]<<" ";
  // cout<<endl;

  int q1;
  scanf("%d",&q1);
  for(int i=1;i<=q1;i++){
    int s1,t1;
    scanf("%d%d",&s1,&t1);
    s1=c[s1];
    t1=c[t1];
    // cout<<s1<<" "<<t1;
    int op=lca(s1,t1);
    if(abs(dis[s1]-dis[op])>0||abs(dis[t1]-dis[op])>0||abs(wi[t1]-wi[op])>0||abs(wi[s1]-wi[op])>0)
      printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}
2022/10/19 19:39
加载中...