hdu3592 World Exhibition --- 差分约束 - c语言编程

TOP

hdu3592 World Exhibition --- 差分约束

2015-01-22 21:13:59 来源: 作者: 【大中小】浏览:38次

Tags：hdu3592 World Exhibition ---差分约束

这题建图没什么特别

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 __int64 using namespace std; #define N 1010 struct 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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：[HDU 1757] A Simple Math Proble..	下一篇：poj 2409 Let it Bead Polya计数

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: