RT

好心人给个代码

我的图直接是原来的图，不加任何节点，每个节点赋初值0，每个节点初始都进队列，

我的开始是是判定到如有某个点被松弛V（顶点数）次，就判定负环，WA

结果加了一个判断过程：

再队列为空的情况下（应该就没负环了），

出了SPFA以后，再来一次对所有边遍历，看有没有可松弛的，有的话就判负

居然AC了

然后再次在其中改代码，该到如果有点可松弛，比如从u指向v有路径可松弛，就看u点是否在队列
中，如果不在，就输出1/0（我要看RE），还真RE了！

怪了，不在队列里还能松弛别得点，搞了整整半天搞不懂，急求指教，或者一个SPFA判负环AC得程序。

我附上我代码：

#include <stdio.h>
#include <stdlib.h>
struct stct0{
  int u,v;
  long w;
}l[200010];
int n;
long m;
int q[1100],inq[1001],reti[1001];
long d[1001],adjg[1001][1000];
main(){
  char typch;     
  int i,a,b,head,tail,flag;
  long j,c,index;
  while(scanf("%d%ld",&n,&m)!=EOF){
    for(i=1;i<=n;i++){
      q[i-1]=i;                
      adjg[i][0]=0;
      inq[i]=1;
      reti[i]=0;
      d[i]=0;
    }//init
    j=0;
    while(m--){
      getchar();
      scanf("%c",&typch);
      if(typch=='P'){
        scanf("%d%d%ld",&a,&b,&c);
        l[j].v=a;
        l[j].u=b;
        l[j].w=-c;
        adjg[b][0]++;
        adjg[b][adjg[b][0]]=j;
        j++;
        l[j].v=b;
        l[j].u=a;
        l[j].w=c;
        adjg[a][0]++;
        adjg[a][adjg[a][0]]=j;
        j++;
      }else{
        scanf("%d%d",&a,&b);
        l[j].v=a;
        l[j].u=b;
        l[j].w=-1;
        adjg[b][0]++;
        adjg[b][adjg[b][0]]=j;
        j++;
      }
    }
    head=0;
    tail=n;
    flag=1;
    while(head!=tail&&flag){
      for(i=adjg[q[head]][0];i>=1;i--){
        index=adjg[q[head]][i];
        if(d[l[index].v]>d[l[index].u]+l[index].w){
          reti[l[index].v]++;
          d[l[index].v]=d[l[index].u]+l[index].w;
          if(!inq[l[index].v]){
            q[tail]=l[index].v;
            inq[l[index].v]=1;
            tail++;
            tail%=1100;
          }
          if(reti[l[index].v]==n){
            flag=0;                      
            break;
          }//negative circle occured
        }//relax & time
      }
      inq[q[head]]=0;
      head++;
      head%=1100;
    }
    
//加的下面这块
if(flag){
      for(i=1;i<=n;i++){
        for(j=adjg[i][0];j>=1;j--){
          if(d[l[adjg[i][j]].v]>d[l[adjg[i][j]].u]+l[adjg[i][j]].w){
            if(!inq[d[l[adjg[i][j]].u]]){
              printf("%d",1/(i-i));//要RE得
            }
            flag=0;
            break;
          }
        }
        if(!flag)
          break;
      }
    }
//加的上面这块
    if(flag)
      printf("Reliable\n");
    else
      printf("Unreliable\n");  
  }     
  return 0;
}

• 我用SPFA居然wrong answer！ (0) heliwen 2009-07-30 10:50:25
  • Re:我用SPFA居然wrong answer！ (40) Vidic15 2009-11-20 00:15:08
    • 正解 (2) slon 2011-05-24 20:23:05
    • Re:我用SPFA居然wrong answer！ (25) lmy199433 2011-10-03 13:07:11