首页 > 代码库 > poj 3169 差分约束

poj 3169 差分约束

2024-07-07 23:17:42   230人阅读

3169

差分约束的是满足多组形如xi-yj<=bk{i,j<n k<m}不等式极值问题，可以转化为单源最短路来求。

在最短路中 d[v]<=d[u]+w(u,v) 可以看出跟上面的不等式很像

通常有两种一种是求满足所有不等式的最大值，还有是最小值。

这篇博客可以参考一下

分析：

题目给出了两种不等式  d[u]+dl >=d[v]       d[u]+dd<=d[v]  要求的是最大值，也就是最短路

对于d[u]+dl>=d[v] 建边(u,vdl) 

对于d[u]+dd<=d[v] 建边(v,u,-dd)

然后跑一边最短路就好了，注意是负权图

如果有负环则无解，有点最短距离未更新为多解，否则为S->e的最短距离

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<vector>
 9 #define maxn 50010
10 #define maxm 100010
11 #define INF 0x3fffffff
12 using namespace std;
13 struct edge{
14     int from,to,w;
15     edge(){}
16     edge(int _u,int _v,int _w){
17         from=_u,to=_v,w=_w;
18     }
19 };
20 edge G[maxm];
21 int V,E;
22 void addedge(int u,int v,int w){
23     G[E++]=edge(u,v,w);
24 }
25 int d[maxn];
26 int n,m;
27 void bellman_ford(int s){
28     V=n;
29     for(int i=0;i<V;++i)d[i]=INF;
30     d[s]=0;
31     while(1){
32         bool flag =false;
33         for(int i=0;i<E;++i){
34             edge e = G[i];
35             if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.w){
36                 d[e.to] = d[e.from]+e.w;
37                 flag = true;
38             }
39         }
40         if(!flag)break;
41     }
42 }
43 bool HaveNagativeLoop(){
44     memset(d,0,sizeof(d));
45     for(int i=0;i<V;++i){
46         for(int j=0;j<E;++j){
47             edge e = G[j];
48             if(d[e.to]>d[e.from]+e.w){
49                 d[e.to] = d[e.from]+e.w;
50                 if(i==V-1)return true;
51             }
52         }
53     }
54     return false;
55 }
56 int ml,md;
57 int main (){
58     while(scanf("%d%d%d",&n,&ml,&md)!=EOF){
59         int u,v,w;
60         E=0;
61         V=n;
62         for(int i=0;i<n-1;++i){
63             addedge(i+1,i,0);
64         }
65         for(int i=0;i<ml;++i){
66             scanf("%d%d%d",&u,&v,&w);
67             addedge(u-1,v-1,w);
68         }
69         for(int i=0;i<md;++i){
70             scanf("%d%d%d",&u,&v,&w);
71             addedge(v-1,u-1,-w);
72         }
73         if(HaveNagativeLoop()){printf("-1\n");continue;}
74         bellman_ford(0);
75         if(d[n-1]==INF)printf("%d\n",-2);
76         else printf("%d\n",d[n-1]);
77     }
78 }
View Code

 

 

 


联系
我们