UVA 11478 Halum(差分约束系统+Bellman



题意:给定一个有向图,每条边都有一个权值。每次你可以选择一个结点v和一个整数d,把所有以v为终点的边的权值减小d,把所有以v为起点的边的权值增加d,最后让所有边的权值的最小值大于零且尽量大。

ps:lrj的书上有个坑,说上说非负,其实原题说要大于0…..wa了好几发

分析:因为不同的操作互不影响,,因此可以按任意顺序实施这些操作。另外,对于同一个点的多次操作可以合并,因此可以令sum(u)为作用于结点u之上的所有d之和。这样,本题的目标就是确定所有的sum(u),使得操作之后所有边权的最小值尽量大。

“最小值最大”使用二分答案的方法。二分答案x之后,问题转化为是否可以让操作完毕后每条边的权值均不小于x。对于边a->b,不难发现操作完毕后它的权值为w(a,b)+sum(a)-sum(b),因此每条边a->b都可以列出一个不等式w(a,b)+sum(a)-sum(b)>=x,移项得sum(b)-sum(a)<=w(a,b)-x。这样,我们实际得到一个差分约束系统。

查分约束系统是指一个不等式组,每个不等式形如xj-xi<=bk,这里的bk是一些事先已知的常数。这个不等式类似于最短路中的不等式d[v]<=d[u]+w(u,v),我们可以用最短路算法求解:对于约束条件xj-xi《=bk,新建一条边i–>j,权值为bk。如果图中有负权环,则差分约束系统无解。

#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>#define eps 1e-4 #define LL long long using namespace std; const int maxn = 500 + 10;const int INF = 0x3f3f3f3f;//Bellman-Ford算法struct Edge {int from, to;int dist;Edge(int u = 0, int v = 0, double d = 0) : from(u), to(v), dist(d) {}};struct BellmanFord{int n, m;vector<Edge> edges;vector<int> G[maxn];bool inq[maxn];int d[maxn];int p[maxn];int cnt[maxn];void init(int n) {this->n = n;for(int i = 0; i < n; i++) G[i].clear();edges.clear();}void AddEdges(int from, int to, int dist) {edges.push_back(Edge(from, to, dist));m = edges.size();G[from].push_back(m-1);}bool bellman_ford(int S) {queue<int> Q;memset(inq, 0, sizeof(inq));memset(cnt, 0, sizeof(cnt));for(int i = 0; i < n; i++) d[i] = INF;d[S] = 0;inq[S] = true;Q.push(S);while(!Q.empty()) {int u = Q.front(); Q.pop();inq[u] = false;for(int i = 0; i < G[u].size(); i++) {Edge& e = edges[G[u][i]];if(d[u]<INF && d[e.to]>d[u]+e.dist) {d[e.to] = d[u] + e.dist;p[e.to] = G[u][i];if(!inq[e.to]) {Q.push(e.to);inq[e.to] = true;if(++cnt[e.to] > n) return false;}}}}return true;}bool negetiveCycle() {queue<int> Q;memset(inq, 0, sizeof(inq));memset(cnt, 0, sizeof(cnt));for(int i = 0; i < n; i++) {d[i] = 0; inq[0] = true; Q.push(i);}while(!Q.empty()) {int u = Q.front(); Q.pop();inq[u] = false;for(int i = 0; i < G[u].size(); i++) {Edge& e = edges[G[u][i]];if(d[e.to]>d[u]+e.dist) {d[e.to] = d[u] + e.dist;p[e.to] = G[u][i];if(!inq[e.to]) {Q.push(e.to);inq[e.to] = true;if(++cnt[e.to] > n) return true;}}}}return false;}} solver; int n, m;bool test(int w) {for(int i = 0; i < m; i++) solver.edges[i].dist -= w;int t = solver.negetiveCycle();for(int i = 0; i < m; i++) solver.edges[i].dist += w;return t;}int kase;int main() {freopen("input.txt", "r", stdin);while(scanf("%d%d", &n, &m) == 2) {solver.init(n);for(int i = 0; i < m; i++) {int u, v, d;cin >> u >> v >> d;u–; v–;solver.AddEdges(u, v, d);}int L = 0, R = 10000;if(test(1)) puts("No Solution");else if(!test(R+5)) puts("Infinite");else {while(L <= R) {int M = (R+L)/2;if(test(M)) R = M – 1;else L = M + 1;}printf("%d\n", R);}}return 0;}

版权声明:本文为博主原创文章,未经博主允许不得转载。

人性最可怜的就是:我们总是梦想着天边的一座奇妙的玫瑰园,

UVA 11478 Halum(差分约束系统+Bellman

相关文章:

你感兴趣的文章:

标签云: