首页 > 代码库 > Intervals---poj1201（差分约束系统）
Intervals---poj1201（差分约束系统）
题目链接：http://poj.org/problem?id=1201
题目说[ai, bi]区间内和点集Z至少有ci个共同元素，那也就是说如果我用Si表示区间[0,i]区间内至少有多少个元素的话，那么Sbi - Sai >= ci,这样我们就构造出来了一系列边，权值为ci，但是这远远不够，因为有很多点依然没有相连接起来（也就是从起点可能根本就还没有到终点的路线）,此时，我们再看看Si的定义，也不难写出0<=Si - Si-1<=1的限制条件，虽然看上去是没有什么意义的条件，但是如果你也把它构造出一系列的边的话，这样从起点到终点的最短路也就顺理成章的出现了。
我们将上面的限制条件写为同意的形式：
Sbi - Sai >= ci
Si - Si-1 >= 0
Si-1 - Si >= -1
因为要求的是最小有多少个，所以要求最长路；
所以求出图中最小点到最大点的最大距离即可；
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <queue>#include <stack>#include <algorithm>#include <map>#include <string>typedef long long LL;#define INF 0x3f3f3f3f#define met(a, b) memset(a, b, sizeof(a))#define N 51500using namespace std;int S, E, vis[N], dist[N];struct node{ int u, v, w, Next;}e[N*3];int Head[N], cnt;void Add(int u, int v, int w){ e[cnt].v = v; e[cnt].w = w; e[cnt].Next = Head[u]; Head[u] = cnt++;}int spfa(){ for(int i=0; i<=E; i++) dist[i] = -INF; met(vis, 0); queue<int> Q; Q.push(S); vis[S] = 1; dist[S] = 0; while(!Q.empty()) { int p = Q.front();Q.pop(); vis[p] = 0; for(int i=Head[p]; i!=-1; i=e[i].Next) { int q = e[i].v; if(dist[q] < dist[p]+e[i].w)///最长路； { dist[q] = dist[p]+e[i].w; if(!vis[q]) { vis[q] = 1; Q.push(q); } } } } return dist[E];}int main(){ int n, u, v, w; while(scanf("%d", &n) != EOF) { met(e, 0); met(Head, -1); cnt = 0; S = INF; E = -INF;///找到对应的起点和终点； for(int i=1; i<=n; i++) { scanf("%d %d %d", &u, &v, &w); Add(u, v+1, w);///u可能等于0，所以v+1比较好； S = min(u, S); E = max(v+1, E); } for(int i=S; i<E; i++)///建立其他边，所以e要开3倍的N； { Add(i, i+1, 0); Add(i+1, i, -1); } int ans = spfa(); printf("%d\n", ans); } return 0;}
Intervals---poj1201（差分约束系统）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。