POJ 2983 Is the Information Reliable?（差分约束系统） - c++编程基础

TOP

POJ 2983 Is the Information Reliable?（差分约束系统）

2015-07-20 17:50:40 来源: 作者: 【大中小】浏览:3次

Tags：POJ 2983 the Information Reliable 差分约束系统

题目地址：POJ 2983

这题刚上来完全不知道跟差分约束系统有什么关系。。。。。后来发现只要判个负环就可以。。

因为假如有冲突的话会形成一个负环。之所以建图加上一个正值一个负值，是因为这样的话，像1 2 4和1 2 3这样的数据就会形成一个负环。这个方法还是很巧妙的。。。然后对于V的那些不清楚的位置，就会跟P的那些等式联立形成一个不等式，然后在用最短路判环的过程中就用松弛来解决。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; const int INF=0x3f3f3f3f; int d[2000], head[2000], cnt, n; struct node { int u, v, w, next; } edge[200000]; void add(int u, int v, int w) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void berman() { memset(d,INF,sizeof(d)); int i, j, flag, k; for(i=1; i
             
              d[j]+edge[k].w) { d[v]=d[j]+edge[k].w; flag=1; } } } if(!flag) break; } flag=0; for(i=0; i
              
               d[edge[i].u]+edge[i].w) { flag=1; break; } } if(flag) printf("Unreliable\n"); else printf("Reliable\n"); } int main() { int m, a, b, c, i; char ch; while(scanf("%d%d",&n,&m)!=EOF) { memset(head,-1,sizeof(head)); cnt=0; while(m--) { getchar(); scanf("%c",&ch); if(ch=='P') { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); add(b,a,c); } else { scanf("%d%d",&a,&b); add(a,b,-1); } } berman(); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：剑指offer面试题31:连续子数组的..	下一篇：POJ训练计划1201_Intervals(差分..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: