首页 > 代码库 > UVA 11478 Bellman-Ford+差分约束系统

UVA 11478 Bellman-Ford+差分约束系统

2024-07-11 05:11:11   220人阅读

【题意】：

给出一张有向图（信息为点数，边数，每条边的起点终点和权值），然后可以让你做任意次如下操作：

选择任意节点v和一个数值d，使以v为终点的边的权值减d，以v为起点的边的权值加d，

最后要满足两个条件：这些边的权值为非负，这些边中权值最小的边的权值尽量大。
【知识点】：

Bellman-Ford+差分约束系统
【题解】：

差分约束系统：是判断不等式组有解的一种方法（具体原理还不甚理解，以后还会具体补充该文章）

例如有若干不等式形如xj-xi<=ak 那么以i为起点j为终点ak为权值建图，然后用Bellman-Ford跑，若能求出最短路，则说明不等式有解，否则则不。

因为操作次序不影响最终结果，故设sum（a）为在点a上进行操作的值的和，那么可以知道操作完毕后边a->b的值为w（a，b）+sum（a）-sum（b）。

然后再设经过一系列操作后这些边中权值最小的边为x，则对任意边满足x<=w（a，b）+sum（a）-sum（b），变形得sum（b）-sum（a）<=w（a，b）-x。

首先判断（未进行操作前最大边的值）+1是否可以作为权值最小的边，若可行则说明每条边的值可以通过操作无限增大。

判断1，若不可行则说明不管怎么进行操作都不能保证所有边都为非负。然后二分权值最小的边。

判断可行即通过查分约束系统。

 

【代码】：

摘自刘汝佳 训练指南

 1 // UVa11478 Halum 2 // Rujia Liu 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7  8 const int INF = 1000000000; 9 const int maxn = 500 + 10;10 const int maxm = 2700 + 10;11 12 struct Edge {13   int to, dist;14 };15 16 // 邻接表写法17 struct BellmanFord {18   int n, m;19   Edge edges[maxm];20   int head[maxn];21   int next[maxm];22   bool inq[maxn];   // 是否在队列中23   int d[maxn];      // s到各个点的距离24   int cnt[maxn];    // 进队次数25 26   void init(int n) {27     this->n = n;28     m = 0;29     memset(head, -1, sizeof(head));30   }31 32   void AddEdge(int from, int to, int dist) {33     next[m] = head[from];34     head[from] = m;35     edges[m++] = (Edge){to, dist};36   }37 38   bool negativeCycle() {39     queue<int> Q;40     memset(inq, 0, sizeof(inq));41     memset(cnt, 0, sizeof(cnt));42     for(int i = 0; i < n; i++) { d[i] = 0; Q.push(i); }43 44     int u;45     while(!Q.empty()) {46       u = Q.front(); Q.pop();47       inq[u] = false;48       for(int i = head[u]; i != -1; i = next[i]) {49         Edge& e = edges[i];50         if(d[e.to] > d[u] + e.dist) {51           d[e.to] = d[u] + e.dist;52           if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }53         }54       }55     }56     return false;57   }58 };59 60 BellmanFord solver;61 62 // 判断在初始差分约束系统的每个不等式右侧同时减去x之后是否有解63 bool test(int x) {64   for(int i = 0; i < solver.m; i++)65     solver.edges[i].dist -= x;66   bool ret = solver.negativeCycle();67   for(int i = 0; i < solver.m; i++)68     solver.edges[i].dist += x;69   return !ret; // 如果有负环，说明差分约束系统无解70 }71 72 int main() {73   int n, m;74   while(scanf("%d%d", &n, &m) == 2) {75     solver.init(n);76     int ub = 0;77     while(m--) {78       int u, v, d;79       scanf("%d%d%d", &u, &v, &d); ub = max(ub, d);80       solver.AddEdge(u-1, v-1, d);81     }82 83     if(test(ub+1)) printf("Infinite\n"); // 如果可以让每条边权都>ub，说明每条边的权都增加了，重复一次会增加得更多...直到无限84     else if(!test(1)) printf("No Solution\n");85     else {86       int L = 2, R = ub, ans = 1;87       while(L <= R) {88         int M = L + (R-L)/2;89         if(test(M)) { ans = M; L = M+1; } else R = M-1;90       }91       printf("%d\n", ans);92     }93   }94   return 0;95 }

 


联系
我们