1.写SPFA,用样例得到的答案是4，debug了一下后发现，可能是因为在变长相等时没有进行更新而导致后面没有更新dist值的max。于是就在一开始使所有点都入队。
我的问题是，什么情况下需要这样做，什么情况下只需要入队一个点就可以了？
代码：（比较喜欢敲回车~）
#include<stdio.h>
int first[500005],next[500005],cc[500005],value[500005],cnt=0;
void add(int a,int b,int c)
{
    int t;
    if(!first[a])
    {
      first[a]=++cnt;
      cc[cnt]=b;
      value[cnt]=c;
    }
    else
    {
      t=first[a];
      while(next[t])
      t=next[t];
      next[t]=++cnt;
      cc[cnt]=b;
      value[cnt]=c;
    }
    
    
}
int v[50005],queue[10000000],dist[50005]={0};
int main()
{
    int n;
    int x,y,z,t;
    int i,m=0;
    int begin=1,end;
    scanf("%d",&n);
    for(i=0;i<=50000;i++)
    {
        add(i,i+1,0);
        add(i+1,i,-1);
    }
    for(i=1;i<=n;i++)
    {
     scanf("%d%d%d",&x,&y,&z);
     if(x>y)
     {
       t=x;
       x=y;
       y=t;
     }
     if(y>m)
     m=y;
     x-=1;
     add(x,y,z);
    }
    for(i=0;i<=m;i++)
    {
    queue[i+1]=i;
    v[i]=1;
    }
    end=m+1;
    while(begin<=end)
    {
        x=queue[begin++];
        v[x]=0;
        for(i=first[x];i;i=next[i])
        {
           if(dist[x]+value[i]>dist[cc[i]])
           {
             dist[cc[i]]=value[i]+dist[x];
             if(!v[cc[i]])
             {
                v[cc[i]]=1;
                queue[++end]=cc[i];
             }
           }
        }
    }
    printf("%d",dist[m]);
    system("pause");
    
}

2.求解释“差分约束系统”这个名字。

• 我所知道的AC解法，不会的同学进来看看 (368) gchxwk 2010-11-06 18:17:49
  • Re:我所知道的AC解法，不会的同学进来看看 (392) YLSB 2010-11-08 20:14:43
    • Re:我所知道的AC解法，不会的同学进来看看 (40) YLSB 2010-11-08 20:16:54
      • Re:我所知道的AC解法，不会的同学进来看看 (44) qwezxc 2010-11-10 07:59:00
  • LZSB (17) gchxwk 2010-11-10 07:58:28
    • Re:LZSB (3) applepi 2010-11-10 07:58:48
  • 胡说八道 (14) applepi 2010-12-22 17:19:03
  • 楼主，该吃药了 (392) palqing 2011-04-07 17:17:18