POJ2983
大家对比一下一个AC和一个RE了得代码，不信可以试试（C语言）

其中四行让我莫名其妙
      d[l[index].v]=d[l[index].u]+l[index].w;//这一行与下三行
     if(d[l[index].v]>d[l[index].u]+l[index].w){
    printf("%d",1/(i-i));//这三行与上一行
    }
（去掉后三行是个AC得，加了是个RE得，这头两行真让我莫名其妙）

从AC到RE只需加刚才那三行代码，在其中我标了注释给大家指出的

这是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;//这一行与下三行
          
//就下面3行，请对比一下上一行与下三行          

    //if(d[l[index].v]>d[l[index].u]+l[index].w){
    //printf("%d",1/(i-i));//这三行与上一行
    //}

//上面三行

          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;
      /*
      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){
          printf("%d",1/(i-i));
        }
      }
      */
      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));
            //}
            flag=0;
            break;
          }
        }
        if(!flag)
          break;
      }
    }
    if(flag)
      printf("Reliable\n");
    else
      printf("Unreliable\n");  
  }     
  return 0;
}

RE得，就加那三行
#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(d[l[index].v]>d[l[index].u]+l[index].w){
            printf("%d",1/(i-i));
          }
          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;
      /*
      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){
          printf("%d",1/(i-i));
        }
      }
      */
      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));
            //}
            flag=0;
            break;
          }
        }
        if(!flag)
          break;
      }
    }
    if(flag)
      printf("Reliable\n");
    else
      printf("Unreliable\n");  
  }     
  return 0;
}

• Re:谁看谁茫然 (32) ZaakDov 2009-06-05 23:26:59
  • 哭了 (36) ZaakDov 2009-06-05 23:27:10