首页 > 代码库 > SGU 298 King Berl VI 差分约束 并使得min(dis[n]-dis[1])
SGU 298 King Berl VI 差分约束 并使得min(dis[n]-dis[1])
题目链接:点击打开链接
题意:
给定n个点m条约束。
下面输出 u v x 表示:
dis[u] - dis[v] >= x
然后建图就是 u->v 边权为-x
输出一个解满足 -10000<= dis[i] <= 10000。
若有多解输出一个 dis[n] - dis[1] 最小的解。
思路:
正图求个最大解,反图求个最小解。
对于一个点的 最大解<最小解,则差分约束无解。
注意:这里所说的最大解最小解是需要确定一个变量的。则这个变量就是(解集中max(dis[i]) = inf)
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <set> #include <math.h> #include <map> #include <queue> using namespace std; #define N 10010 #define M 100010 #define inf 10000 struct Edge{ int to, dis, nex; }; int inq[N], Tim[N]; int n, m; bool spfa(int head[], Edge edge[], int dis[]){ queue<int> q; for(int i = 1; i <= n; i++) Tim[i] = 0, inq[i] = 1, q.push(i); while(!q.empty()){ int u = q.front(); q.pop(); inq[u] = 0; for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; if(dis[v] > dis[u] + edge[i].dis) { dis[v] = dis[u]+edge[i].dis; if(!inq[v]) { Tim[v]++; if(Tim[v] > n) return false; inq[v] = 1; q.push(v); } } } } return true; } Edge edge[M], Fedge[M]; int head[N], edgenum, fan[N]; void init(){memset(head, -1, sizeof head); memset(fan, -1, sizeof fan); edgenum = 0; } void add(int u, int v, int d){ Edge E = {v, d, head[u]}; edge[edgenum] = E; head[u] = edgenum; Edge E2 = {u, d, fan[v]}; Fedge[edgenum] = E2; fan[v] = edgenum++; } int disg[N], disr[N]; int solve(){ init(); int u, v, d; while(m--){ scanf("%d %d %d", &u, &v, &d); add(u, v, -d); } for(int i = 1; i <= n; i++) disg[i] = inf; if(spfa(head, edge, disg)==false) return -1; for(int i = 1; i <= n; i++) disr[i] = inf; if(spfa(fan, Fedge, disr)==false) return -1; for(int i = 1; i <= n; i++) if(disg[i] < -disr[i]) return -1; disg[n] = -disr[n]; spfa(head, edge, disg); for(int i = 1; i <= n; i++)printf("%d%c", disg[i], i==n?'\n':' '); return 0; } int main(){ while(cin>>n>>m) if(solve()==-1)puts("-1"); return 0; } /* 3 3 1 2 1 2 1 1 3 1 2 3 3 1 2 1 2 1 -1 3 1 2 3 3 1 2 1 2 1 -1 1 3 2 */
SGU 298 King Berl VI 差分约束 并使得min(dis[n]-dis[1])
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。