hdu3592 World Exhibition --- 差分约束-白红宇

hdu3592 World Exhibition --- 差分约束

阅读量：6588 次

发布时间：2019-06-24

本文共 1324 字，大约阅读时间需要 4 分钟。

这题建图没什么特别

x个条件：Sb-Sa<=c

y个条件：Sa-Sb<=-c

题目问的是。1和n之间的关系。

有负环的话，整个就不可能成立，输出-1

假设图是连通的（1到n是连通的），就输出d[n]

不连通就是题目中说-2的情况。

原来我们建图一般加入一个附加结点，或者開始就把全部点入队，就是考虑到不连通的问题，所以加入一个没有意义的条件。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #define inf 0x3f3f3f3f#define eps 1e-6#define ll __int64using namespace std;#define N 1010struct node{ int v,w,next;}e[30020];int d[N],inq[N],outq[N],n,head[N],h;void addedge(int a,int b,int c){ e[h].v=b; e[h].w=c; e[h].next=head[a]; head[a]=h++;}int spfa(int s){ memset(d,0x3f,sizeof d); memset(inq,0,sizeof inq); memset(outq,0,sizeof outq); d[s]=0;inq[s]=1; queue
              
                q; q.push(s); int i,x; while(!q.empty()) { x=q.front(); q.pop(); inq[x]=0; outq[x]++; if(outq[x]>n) return 0; for(i=head[x];i!=-1;i=e[i].next) { if(d[e[i].v]>d[x]+e[i].w) { d[e[i].v]=d[x]+e[i].w; if(!inq[e[i].v]) { inq[e[i].v]=1; q.push(e[i].v); } } } } return 1;}void init(){ memset(head,-1,sizeof head); h=0;}int main(){ int T,a,b,c,x,y; scanf("%d",&T); while(T--) { init(); scanf("%d%d%d",&n,&x,&y); while(x--) { scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); } while(y--) { scanf("%d%d%d",&a,&b,&c); addedge(b,a,-c); } if(!spfa(1)) printf("-1\n"); else if(d[n]!=inf) printf("%d\n",d[n]); else printf("-2\n"); } return 0;}