https://www.cnblogs.com/31415926535x/p/10463112.html
很早之前学最短路的时候就看了一眼差分约束，，当时以为这种问题不怎么会出现，，而且当时为了只为了学最短路，，所以就没有怎么做题，，知道是什么，但是不会建图使用，， 然后上一次做cf就碰到了，，虽然那道题不只是差分约束能解决还卡时间，，但是万一以后还出现这种题，，只是知道是这个类型的题却不知道如何下手也相当于是不会啊，，所以抽时间重新看了看这块的内容，，做几道题，，顺便背一背最短路的板子，，好久敲最短路的板子都已经忘记了，，
感觉这一块的东西最主要的是建图吧，，很多这样的题的解法都不止一种，，差分约束只是其中一种，，因为使用spfa实现的，，所以也很容易被卡，，
<!-- more -->概念
这里的东西我是先参考这篇博客的还有这里 因为之前看过差分约束，，还有印象，，所以上手很快，，纯理论性东西算法导论等等的地方讲的很详细，，
首先差分约束主要是解决 不等式组的求解，，其中这些不等式组的特征是 $x_i-x_j \leq or \geq K_i(i,j \in [1, n], k \in [1, m])$，，
- 求 $x_n-x_0$的最大值就是求 $x_n$ 到 $x_0$的最短路， $x_i-x_j \leq K_i$
- 求 $x_n-x_0$的最小值就是求 $x_n$ 到 $x_0$的最长路， $x_i-x_j \geq K_i$
建图都是建 $x_j$ -> $x_i$ 的边，权值为K
有些题目还有一些隐藏的条件，，比如说 $x_i-x_{i-1} \leq K_i$等等的约束条件，，一并加上就行了，
要是出现符号不一致的就两边取相反数，，把符号化一致就行，，（这样会出现负权的边，，所以要用spfa来解，，），，
出现 $x_i-x_j < K$ 的话可以化成 $x_i-x_j \leq K + 1$的形式(都是整数的情况下)，，
判断有无解的话就判断建的图有无环就行了，，，
例题
poj-1201-Intervals
题意
题意大概就是，给你n个区间 $[l_i,r_i]$ 要求这些区间内必须要几个数 $C_i$，问你满足这些区间的最少的数，，，
看评论区里很多人都是贪心+线段树（树状数组）做的，，
用差分约束的话就是将题目所给的东西转化成若干个不等式，，然后明白要求什么，，找出隐藏的条件，建图求解，，
这道题我们用 $dis[i]$ 表示0~i这个区间至少要选几个数（类似前缀和的思想），，，然后任意一个区间就可以表示为 $dis[r]-dis[l - 1] \geq c_i$ ，，题目的隐藏条件是相邻两点直接的个数是0或1，，也就是 $0 \leq dis[i]-dis[i-1] \leq 1$，因为对于0这个点出这样无法表示(dis[-1])，，所以对每一个点加一（向右偏移一个位置），，，最后求最长路就行了，，，
代码
1//#include <bits/stdc++.h> 2#include <iostream> 3#include <cstdio> 4#include <cstdlib> 5#include <string.h> 6#include <algorithm> 7#include <queue> 8#define aaa cout<<233<<endl; 9#define endl '\n' 10#define pb push_back 11using namespace std; 12typedef long long ll; 13typedef unsigned long long ull; 14typedef pair<int, int> pii; 15const int inf = 0x3f3f3f3f;//1061109567 16const ll linf = 0x3f3f3f3f3f3f3f; 17const double eps = 1e-6; 18const double pi = 3.14159265358979; 19const int maxn = 1e5 + 5; 20const int maxm = 2e5 + 5; 21const ll mod = 1e9 + 7; 22 23struct edge 24{ 25 int v; 26 int cost; 27 edge(int _v = 0, int _cost = 0):v(_v), cost(_cost){} 28}; 29vector<edge> e[maxn]; 30void addedge(int u, int v, int w) 31{ 32 e[u].pb(edge(v, w)); 33} 34bool vis[maxn]; 35int cnt[maxn]; 36int dis[maxn]; 37bool spfa(int s, int n) 38{ 39 memset(vis, false, sizeof vis); 40 memset(cnt, 0, sizeof cnt); 41 cnt[s] = 1; 42 for(int i = 1; i <= n; ++i)dis[i] = -inf; 43 vis[s] = true; 44 dis[s] = 0; 45 queue<int> q; 46 while(!q.empty())q.pop(); 47 q.push(s); 48 while(!q.empty()) 49 { 50 int u = q.front();q.pop(); 51 vis[u] = false; 52 for(int i = 0; i < e[u].size(); ++i) 53 { 54 int v = e[u][i].v; 55 if(dis[v] < dis[u] + e[u][i].cost) 56 { 57 dis[v] = dis[u] + e[u][i].cost; 58 if(!vis[v]) 59 { 60 vis[v] = true; 61 q.push(v); 62 if(++cnt[v] > n)return false; 63 } 64 } 65 } 66 } 67 return true; 68} 69int main() 70{ 71// freopen("233.in" , "r" , stdin); 72// freopen("233.out" , "w" , stdout); 73// ios_base::sync_with_stdio(0); 74// cin.tie(0);cout.tie(0); 75 int n;scanf("%d", &n); 76 int mi = inf, mx = 0, u, v, w; 77 for(int i = 1; i <= n; ++i) 78 { 79 scanf("%d%d%d", &u, &v, &w); 80 addedge(u, v + 1, w); 81 mi = min(mi, u); 82 mx = max(mx, v); 83 } 84 ++mx; 85 for(int i = mi; i <= mx; ++i) 86 { 87 addedge(i, i + 1, 0); 88 addedge(i + 1, i, -1); 89 } 90 spfa(mi, mx); 91 printf("%d\n", dis[mx]); 92 return 0; 93}
poj-1275-Cashier Employment
题意
题意是一天之内24个小时0点到23点，某个时间点需要的营业员的个数 $r[i]$ 给你，然后有一些应聘的人，他们开始工作的时间 $a[i]$ 给你，，每个人可以从开始的那个时间段工作8个小时，，然后问你最少应该聘用多少个人使得每个时间段的人数 $r[i]$ 是足够的，，
分析
乍一看这题不知道怎么下手，，就算是知道这是一道差分约束的题也不知道图怎么建，，
我的感觉是首先要 找出一个属性使得它在不同两个的状态下的满足的条件不同（也就是题目要求什么，就找什么关系（二项式），，也就是我们后面建图时的点与点之间的关系，，而且是差的不等关系，，也就是构建出一个差分约束系统，，而这个属性一般也就是我们要求的最值的一种最宽的情况，，（ $x_n$ 到 $x_0$的最值）
对于这道题来说，题目要我们求一天之内需要的最少的人数 $sum$ ，，也就是0点到23点的最小值，，这样我们就能看出我们要列出一些 时间段 内的约束条件，，用 $dis[i]$ 表示0点到i点这段时间内至少需要人数，，（又是前缀和的思想），，，这样一段时间内至少需要的人数就是 $dis[i] - dis[j] \leq K$ ，，
一个员工只能工作8个小时，所以我们可以得出：从i-8到i这段时间内工作的人数至少要大于i这个时间段内 $r[i]$ 所需的人数 $dis[i]-dis[i-8] \geq r[i]$，此时的 $i \geq 7$；
对于 $i \leq 7$ 的情况，我们可以推出 $sum-dis[i+16] + s[i] \geq r[i]$
同时对于每一个小时内的最多的工作人数 $mp[i]$ 是确定的，，也就是说， $0 \leq dis[i]-dis[i-1] \leq mp[i]$
一整天的工作人数满足： $dis[24]-dis[0] \geq sum$
上面一个不等式中有一个未知量sum，，它的取值是0~n，，可以二分枚举这个sum多次建图求出最小的sum，，，
代码
1//hdu 2//#include <bits/stdc++.h> 3#include <iostream> 4#include <cstdio> 5#include <cstdlib> 6#include <string.h> 7#include <algorithm> 8#include <queue> 9#include <map> 10#define aaa cout<<233<<endl; 11#define endl '\n' 12#define pb push_back 13using namespace std; 14typedef long long ll; 15typedef unsigned long long ull; 16typedef pair<int, int> pii; 17const int inf = 0x3f3f3f3f;//1061109567 18const ll linf = 0x3f3f3f3f3f3f3f; 19const double eps = 1e-6; 20const double pi = 3.14159265358979; 21const int maxn = 1e5 + 5; 22const int maxm = 2e5 + 5; 23const ll mod = 1e9 + 7; 24struct edge 25{ 26 int to, next, w; 27}edge[maxn]; 28int head[maxn], tot; 29void addedge(int u, int v, int w) 30{ 31 edge[tot].to = v; edge[tot].next = head[u]; edge[tot].w = w; head[u] = tot++; 32} 33void init() 34{ 35 tot = 0; 36 memset(head, -1, sizeof head); 37} 38bool vis[maxn]; 39int dis[maxn], cnt[maxn]; 40bool spfa(int s, int n) 41{ 42 memset(vis, false, sizeof vis); 43 memset(cnt, 0, sizeof cnt); 44 for(int i = 0; i <= n; ++i)dis[i] = -inf; 45 vis[s] = true; 46 dis[s] = 0; 47 cnt[s] = 1; 48 queue<int> q; 49 while(!q.empty())q.pop(); 50 q.push(s); 51 while(!q.empty()) 52 { 53 int u = q.front(); q.pop(); 54 vis[u] = false; 55 //if(u == 24 && dis[u] > m)return 0; 56 for(int i = head[u]; ~i; i = edge[i].next) 57 { 58 int v = edge[i].to; 59 int w = edge[i].w; 60 if(dis[v] < dis[u] + w) 61 { 62 dis[v] = dis[u] + w; 63 if(!vis[v]) 64 { 65 vis[v] = true; 66 q.push(v); 67 if(++cnt[v] > n)return false; 68 } 69 } 70 } 71 } 72 return true; 73} 74int r[30], a[maxn]; 75map<int, int> mp; 76int check(int m) 77{ 78 init(); 79 for(int i = 0; i <= 23; ++i) 80 { 81 addedge(i, i + 1, 0); 82 addedge(i + 1, i, -mp[i]); 83 } 84 for(int i = 7; i <= 23; ++i) 85 addedge(i - 8 + 1, i + 1, r[i]); 86 for(int i = 0; i < 7; ++i) 87 addedge(i + 16 + 1, i + 1, r[i] - m); 88 addedge(0, 24, m); 89 addedge(24, 0, -m); 90 if(spfa(0, 30)) 91 return dis[24]; 92 else 93 return 0; 94} 95int main() 96{ 97// freopen("233.in" , "r" , stdin); 98// freopen("233.out" , "w" , stdout); 99// ios_base::sync_with_stdio(0); 100// cin.tie(0);cout.tie(0); 101 int t;scanf("%d", &t); 102 while(t--) 103 { 104 for(int i = 0; i <= 23; ++i)scanf("%d", &r[i]); 105 int n;scanf("%d", &n); 106 for(int i = 1; i <= n; ++i)scanf("%d", &a[i]); 107 for(int i = 1; i <= n; ++i)++mp[a[i]]; 108 int l = 0, r = n + 1; 109 int ans = 0; 110 //for(int i = 1; i <= n; ++i)cout << check(i) << endl;return 0 ; 111 while(l + 1 < r) 112 { 113 int m = (l + r) >> 1; 114 int flag = check(m); 115 //cout << l << r << m << flag << endl; 116 if(m == flag) 117 { 118 r = m; 119 ans = m; 120 } 121 else 122 l = m; 123 } 124 if(l >= n) 125 printf("No Solution\n"); 126 else 127 printf("%d\n", ans); 128 } 129 return 0; 130} 131//1 132//1 0 3 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 133//5 134//0 135//23 136//22 137//1 138//10
hdu-3440-House Man
题意
题意大概是一个人可以在各个屋顶上跳，，但是必须要跳比现在的高的屋顶，，他可以不改变初始顺序的情况下移动房子来改变他们的距离，，它最大的跳跃距离是d，，然后问你能不能从最矮的房子跳到最高的房子，，如果能，求出最大的这两个房子间的距离
分析
首先是建图，，我们用 $dis[i]$ 表示第1栋房子到第i栋房子之间的最大距离，，然后跑源点是最矮那栋房子的最短路就行了
对于每栋房子，，我们连一条矮房子i到较高房子j的边表示 $dis[j]-dis[i] \leq d$，，注意这里为了保证次序不变，，如果i的编号大于了j，，说明i栋房子在j的右边，，这样 $dis[i] \geq dis[j]$，，上面那个式子就是负的，，不成立（也就是无解），，所以要判断一下，，，
还有一个隐藏条件： 相邻两栋房子之间的距离一定是 $dis[i+1] > dis[i]$，，也就是： $dis[i] - dis[i+1] \leq -1$，，所以建边(i+1)->i权值为-1
代码
没尝试过栈实现的spfa，，据说快一些，，大概是队列时间的三分之一左右，，
普通的队列实现
1//hdu 2//#include <bits/stdc++.h> 3#include <iostream> 4#include <cstdio> 5#include <cstdlib> 6#include <string.h> 7#include <algorithm> 8#include <queue> 9#include <map> 10#define aaa cout<<233<<endl; 11#define endl '\n' 12#define pb push_back 13using namespace std; 14typedef long long ll; 15typedef unsigned long long ull; 16typedef pair<int, int> pii; 17const int inf = 0x3f3f3f3f;//1061109567 18const ll linf = 0x3f3f3f3f3f3f3f; 19const double eps = 1e-6; 20const double pi = 3.14159265358979; 21const int maxn = 1e5 + 5; 22const int maxm = 2e5 + 5; 23const ll mod = 1e9 + 7; 24struct edge 25{ 26 int to, next, w; 27}edge[maxn]; 28int head[maxn], tot; 29void init() 30{ 31 tot = 0; 32 memset(head, -1, sizeof head); 33} 34void addedge(int u, int v, int w) 35{ 36 edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++; 37} 38bool vis[maxn]; 39int dis[maxn], cnt[maxn]; 40bool spfa(int s, int n) 41{ 42 for(int i = 0; i <= n; ++i)vis[i] = false; 43 for(int i = 0; i <= n; ++i)cnt[i] = 0; 44 for(int i = 0; i <= n; ++i)dis[i] = inf; 45 vis[s] = true; 46 cnt[s] = 1; 47 dis[s] = 0; 48 queue<int> q; 49 while(!q.empty())q.pop(); 50 q.push(s); 51 while(!q.empty()) 52 { 53 int u = q.front();q.pop(); 54 vis[u] = false; 55 for(int i = head[u]; ~i; i = edge[i].next) 56 { 57 int v = edge[i].to; 58 int w = edge[i].w; 59 if(dis[v] > dis[u] + w) 60 { 61 dis[v] = dis[u] + w; 62 if(!vis[v]) 63 { 64 vis[v] = true; 65 q.push(v); 66 if(++cnt[v] > n)return false; 67 } 68 } 69 } 70 } 71 return true; 72} 73struct node 74{ 75 int h, id; 76 const bool operator<(const node &r)const 77 { 78 return h < r.h; 79 } 80}node[maxn]; 81int main() 82{ 83// freopen("233.in" , "r" , stdin); 84// freopen("233.out" , "w" , stdout); 85 int t;scanf("%d", &t); 86 for(int ca = 1; ca <= t; ++ca) 87 { 88 int n, d; 89 scanf("%d%d", &n, &d); 90 for(int i = 1; i <= n; ++i) 91 { 92 node[i].id = i; 93 scanf("%d", &node[i].h); 94 } 95 sort(node + 1, node + 1 + n); 96 init(); 97 98 bool flag = true; 99 for(int i = 1; i <= n - 1 && flag; ++i) 100 { 101 addedge(i + 1, i, -1); 102 int u = min(node[i].id, node[i + 1].id); 103 int v = max(node[i].id, node[i + 1].id); 104 if(u > v)flag = false; 105 addedge(u, v, d); 106 } 107 printf("Case %d: ", ca); 108 int s = min(node[1].id, node[n].id); 109 int t = max(node[1].id, node[n].id); 110 if(!flag || !spfa(s, n))printf("-1\n"); 111 else printf("%d\n", dis[t]); 112 } 113 return 0; 114}
队列实现
1//hdu 2//#include <bits/stdc++.h> 3#include <iostream> 4#include <cstdio> 5#include <cstdlib> 6#include <string.h> 7#include <algorithm> 8#include <queue> 9#include <map> 10#define aaa cout<<233<<endl; 11#define endl '\n' 12#define pb push_back 13using namespace std; 14typedef long long ll; 15typedef unsigned long long ull; 16typedef pair<int, int> pii; 17const int inf = 0x3f3f3f3f;//1061109567 18const ll linf = 0x3f3f3f3f3f3f3f; 19const double eps = 1e-6; 20const double pi = 3.14159265358979; 21const int maxn = 1e5 + 5; 22const int maxm = 2e5 + 5; 23const ll mod = 1e9 + 7; 24struct edge 25{ 26 int to, next, w; 27}edge[maxn]; 28int head[maxn], tot; 29void init() 30{ 31 tot = 0; 32 memset(head, -1, sizeof head); 33} 34void addedge(int u, int v, int w) 35{ 36 edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++; 37} 38bool vis[maxn]; 39int dis[maxn], cnt[maxn]; 40bool spfa(int s, int n) 41{ 42 for(int i = 0; i <= n; ++i)vis[i] = false; 43 for(int i = 0; i <= n; ++i)cnt[i] = 0; 44 for(int i = 0; i <= n; ++i)dis[i] = inf; 45 vis[s] = true; 46 cnt[s] = 1; 47 dis[s] = 0; 48 queue<int> q; 49 while(!q.empty())q.pop(); 50 q.push(s); 51 while(!q.empty()) 52 { 53 int u = q.front();q.pop(); 54 vis[u] = false; 55 for(int i = head[u]; ~i; i = edge[i].next) 56 { 57 int v = edge[i].to; 58 int w = edge[i].w; 59 if(dis[v] > dis[u] + w) 60 { 61 dis[v] = dis[u] + w; 62 if(!vis[v]) 63 { 64 vis[v] = true; 65 q.push(v); 66 if(++cnt[v] > n)return false; 67 } 68 } 69 } 70 } 71 return true; 72} 73struct node 74{ 75 int h, id; 76 const bool operator<(const node &r)const 77 { 78 return h < r.h; 79 } 80}node[maxn]; 81int main() 82{ 83// freopen("233.in" , "r" , stdin); 84// freopen("233.out" , "w" , stdout); 85 int t;scanf("%d", &t); 86 for(int ca = 1; ca <= t; ++ca) 87 { 88 int n, d; 89 scanf("%d%d", &n, &d); 90 for(int i = 1; i <= n; ++i) 91 { 92 node[i].id = i; 93 scanf("%d", &node[i].h); 94 } 95 sort(node + 1, node + 1 + n); 96 init(); 97 98 bool flag = true; 99 for(int i = 1; i <= n - 1 && flag; ++i) 100 { 101 addedge(i + 1, i, -1); 102 int u = min(node[i].id, node[i + 1].id); 103 int v = max(node[i].id, node[i + 1].id); 104 if(u > v)flag = false; 105 addedge(u, v, d); 106 } 107 printf("Case %d: ", ca); 108 int s = min(node[1].id, node[n].id); 109 int t = max(node[1].id, node[n].id); 110 if(!flag || !spfa(s, n))printf("-1\n"); 111 else printf("%d\n", dis[t]); 112 } 113 return 0; 114}
poj-3169-Layout
题意
一排牛，，有一些牛之间的距离不能超出d，有一些牛的距离不能小于d，，问你第一头和最后一头牛直接的距离的最大值是多少
分析
简单的差分约束，，直接建图就行了，，，(貌似不加相邻两头之间距离大于1这个条件也能过)
图有环为-1，，距离是inf为-2，其他的就是dis[n]，，
代码
1//hdu 2//#include <bits/stdc++.h> 3#include <iostream> 4#include <cstdio> 5#include <cstdlib> 6#include <string.h> 7#include <algorithm> 8#include <queue> 9#include <map> 10#define aaa cout<<233<<endl; 11#define endl '\n' 12#define pb push_back 13using namespace std; 14typedef long long ll; 15typedef unsigned long long ull; 16typedef pair<int, int> pii; 17const int inf = 0x3f3f3f3f;//1061109567 18const ll linf = 0x3f3f3f3f3f3f3f; 19const double eps = 1e-6; 20const double pi = 3.14159265358979; 21const int maxn = 1e6 + 5; 22const int maxm = 2e5 + 5; 23const ll mod = 1e9 + 7; 24struct edge 25{ 26 int to, next, w; 27}edge[maxn]; 28int head[maxn], tot; 29void init() 30{ 31 tot = 0; 32 memset(head, -1, sizeof head); 33} 34void addedge(int u, int v, int w) 35{ 36 edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++; 37} 38bool vis[maxn]; 39int dis[maxn], cnt[maxn], sta[maxn]; 40int spfa(int s, int n) 41{ 42 for(int i = 1; i <= n; ++i)vis[i] = false; 43 for(int i = 1; i <= n; ++i)dis[i] = inf; 44 for(int i = 1; i <= n; ++i)cnt[i] = 0; 45 vis[s] = true; 46 cnt[s] = 1; 47 dis[s] = 0; 48 int top = -1; 49 sta[++top] = s; 50 while(~top) 51 { 52 int u = sta[top--]; 53 vis[u] = false; 54 for(int i = head[u]; ~i; i = edge[i].next) 55 { 56 int v = edge[i].to; 57 int w = edge[i].w; 58 if(dis[v] > dis[u] + w) 59 { 60 dis[v] = dis[u] + w; 61 if(!vis[v]) 62 { 63 vis[v] = true; 64 sta[++top] = v; 65 if(++cnt[v] > n)return -1; 66 } 67 } 68 } 69 } 70 if(dis[n] == inf)return -2; 71 return dis[n]; 72} 73int main() 74{ 75// freopen("233.in" , "r" , stdin); 76// freopen("233.out" , "w" , stdout); 77// ios_base::sync_with_stdio(0); 78// cin.tie(0);cout.tie(0); 79 int n, ml, md; 80 scanf("%d%d%d", &n, &ml, &md); 81 int u, v, w; 82 init(); 83 for(int i = 1; i <= ml; ++i) 84 { 85 scanf("%d%d%d", &u, &v, &w); 86 if(u > v)swap(u, v); 87 addedge(u, v, w); 88 } 89 for(int i = 1; i <= md; ++i) 90 { 91 scanf("%d%d%d", &u, &v, &w); 92 if(u < v)swap(u, v); 93 addedge(u, v, -w); 94 } 95// for(int i = 1; i <= n; ++i) 96// addedge(i + 1, i, 0); 97 printf("%d\n", spfa(1, n)); 98 return 0; 99}
poj-1364-King
题意
题意是一个序列的一些子序列的和与k的大小关系给你，然后问你原序列的与一个数k的大小关系是否能确定出来，，
分析
还是前缀和的思想，$dis[i]$ 表示第一个数到第i个数的和，，那么子序列[i,j]的和就表示为 $dis[j]-dis[i]$，，题目又给了一些子序列和与一个数的大小关系，也就是： $dis[j] - dis[i] < or > K_i$，，用这个条件建图，，因为最后的图可能不连通，所以再加一个源点到所有点为0的边，，
注意，题目给的是每个子序列的起点和它的长度，，大小关系没有等于的情况，，加一减一就行了，，
代码
1//hdu 2//#include <bits/stdc++.h> 3#include <iostream> 4#include <cstdio> 5#include <cstdlib> 6#include <string.h> 7#include <algorithm> 8#include <queue> 9#include <map> 10#define aaa cout<<233<<endl; 11#define endl '\n' 12#define pb push_back 13using namespace std; 14typedef long long ll; 15typedef unsigned long long ull; 16typedef pair<int, int> pii; 17const int inf = 0x3f3f3f3f;//1061109567 18const ll linf = 0x3f3f3f3f3f3f3f; 19const double eps = 1e-6; 20const double pi = 3.14159265358979; 21const int maxn = 1e6 + 5; 22const int maxm = 2e5 + 5; 23const ll mod = 1e9 + 7; 24struct edge 25{ 26 int to, w, next; 27}edge[maxn]; 28int head[maxn], tot; 29void init() 30{ 31 tot = 0; 32 memset(head, -1, sizeof head); 33} 34void addedge(int u, int v, int w) 35{ 36 edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++; 37} 38bool vis[maxn]; 39int dis[maxn], cnt[maxn], sta[maxn]; 40bool spfa(int s, int n) 41{ 42 for(int i = 0; i <= n; ++i)vis[i] = false; 43 for(int i = 0; i <= n; ++i)dis[i] = inf; 44 for(int i = 0; i <= n; ++i)cnt[i] = 0; 45 vis[s] = true; 46 cnt[s] = 1; 47 dis[s] = 0; 48 int top = -1; 49 sta[++top] = s; 50 while(~top) 51 { 52 int u = sta[top--]; 53 vis[u] = false; 54 for(int i = head[u]; ~i; i = edge[i].next) 55 { 56 int v = edge[i].to; 57 int w = edge[i].w; 58 if(dis[v] > dis[u] + w) 59 { 60 dis[v] = dis[u] + w; 61 if(!vis[v]) 62 { 63 vis[v] = true; 64 sta[++top] = v; 65 if(++cnt[v] > n)return false; 66 } 67 } 68 } 69 } 70 return true; 71} 72int main() 73{ 74// freopen("233.in" , "r" , stdin); 75// freopen("233.out" , "w" , stdout); 76// ios_base::sync_with_stdio(0); 77// cin.tie(0);cout.tie(0); 78 int n, m; 79 while(~scanf("%d", &n) && n) 80 { 81 scanf("%d", &m); 82 int u, v, d; 83 char s[2]; 84 init(); 85 for(int i = 1; i <= m; ++i) 86 { 87 scanf("%d %d %s %d", &u, &v, s, &d); 88 if(s[0] == 'g') 89 addedge(u + v, u - 1, -d - 1); 90 else 91 addedge(u - 1, u + v, d - 1); 92 } 93 for(int i = 0; i <= n; ++i) 94 addedge(n + 1, i, 0); 95 if(spfa(n + 1, n + 1)) 96 printf("lamentable kingdom\n"); 97 else 98 printf("successful conspiracy\n"); 99 } 100 return 0; 101}
poj-2983-Is the Information Reliable?
题意
n个站点排成一排，，给出一些描述信息
两个站点之间如果是P，，说明距离是确定的x
如果是V，，距离至少是1
问是否存在这样一个序列满足上面的条件
dis[i]表示第i站所在的位置距离第一个的距离，，这样两站的描述信息就能化成很多的不等式来表示，，建图判断是否存在环就行了，，注意原图可能不连通，所以加一个源点就行了，，，
按道理说栈实现spfa应该比队列实现的快一些，，但是这道题用栈实现t了（不止我一个人），，emmm迷一遍的操作，，队列可过，，
1//hdu 2//#include <bits/stdc++.h> 3#include <iostream> 4#include <cstdio> 5#include <cstdlib> 6#include <string.h> 7#include <algorithm> 8#include <queue> 9#include <map> 10#define aaa cout<<233<<endl; 11#define endl '\n' 12#define pb push_back 13using namespace std; 14typedef long long ll; 15typedef unsigned long long ull; 16typedef pair<int, int> pii; 17const int inf = 0x3f3f3f3f;//1061109567 18const ll linf = 0x3f3f3f3f3f3f3f; 19const double eps = 1e-6; 20const double pi = 3.14159265358979; 21const int maxn = 1e6 + 5; 22const int maxm = 2e5 + 5; 23const ll mod = 1e9 + 7; 24struct edge 25{ 26 int to, next, w; 27}edge[maxn]; 28int head[maxn], tot; 29void init() 30{ 31 tot = 0; 32 memset(head, -1, sizeof head); 33} 34void addedge(int u, int v, int w) 35{ 36 edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++; 37} 38bool vis[maxn]; 39int dis[maxn], cnt[maxn], sta[maxn]; 40bool spfa(int s, int n) 41{ 42 for(int i = 0; i <= n; ++i)vis[i] = false; 43 for(int i = 0; i <= n; ++i)cnt[i] = 0; 44 for(int i = 0; i <= n; ++i)dis[i] = -inf; 45 vis[s] = true; 46 cnt[s] = 1; 47 dis[s] = 0; 48// int top = -1; 49// sta[++top] = s; 50 queue<int> q; 51 while(!q.empty())q.pop(); 52 q.push(s); 53 //while(~top) 54 while(!q.empty()) 55 { 56// int u = sta[top--]; 57 int u = q.front(); q.pop(); 58 vis[u] = false; 59 for(int i = head[u]; ~i; i = edge[i].next) 60 { 61 int v = edge[i].to; 62 int w = edge[i].w; 63 if(dis[v] < dis[u] + w) 64 { 65 dis[v] = dis[u] + w; 66 if(!vis[v]) 67 { 68 vis[v] = true; 69 //sta[++top] = v; 70 q.push(v); 71 if(++cnt[v] > n)return false; 72 } 73 } 74 } 75 } 76 return true; 77} 78int main() 79{ 80// freopen("233.in" , "r" , stdin); 81// freopen("233.out" , "w" , stdout); 82// ios_base::sync_with_stdio(0); 83// cin.tie(0);cout.tie(0); 84 int n, m; 85 while(~scanf("%d%d", &n, &m)) 86 { 87 init(); 88 for(int i = 1; i <= m; ++i) 89 { 90 int u, v, w; 91 char pv; 92 w = 1; 93 scanf(" %c %d %d", &pv, &u, &v); 94 if(pv == 'P') 95 { 96 scanf("%d", &w); 97 addedge(v, u, -w); 98 } 99 addedge(u, v, w); 100 } 101 for(int i = 1; i <= n; ++i) 102 addedge(0, i, 0); 103 if(spfa(0, n)) 104 printf("Reliable\n"); 105 else 106 printf("Unreliable\n"); 107 } 108 return 0; 109}
codeofeces-1131d-D. Gourmet choice
做这些差分约束的题的主要的原因就是这道cf的题，，当时比赛的时候就有人说是差分约束的题，，但是因为我只是了解这块内容，，但是实际的题目完全没有写过，，所以看到题也没有什么思路，，就放弃了，，
现在再看这道题，，感觉十分的简单，，，
题意
大概的意思就是有n+m个点，，他们直接的大小关系已知（具体大或小多少没有说），，，然后问你能不能给每一个点赋一个值使得满足所给的关系，，
分析
一种解法是用并查集缩点后跑一边拓扑排序，，最后求得的最长链就是答案，，，
用差分约束解的话就是用所给的关系直接建图就行了，，对于i->j大于就正的建一条边，小于就反着建一条边，，等于就建两条就行了，，，
因为图可能是不连通的，，所以再弄个源点，连到每个点就行了，，，
因为最后要的是每一的节点一个数，，而且尽可能小，，所以就找出dis数组里距离源点最小的那个数，，然后每一个点减去这个最小的数就是最后要赋的值了，，，
对了这题用链式前向星来建图会T，，，换邻接表就好了，，，（不是说链式前向星的效率更高吗，，，emmmm，，迷，，，就像那道用栈的spfaT掉用队列就过了一样迷，，，
代码
1//cf 2#include <bits/stdc++.h> 3//#include <iostream> 4//#include <cstdio> 5//#include <cstdlib> 6//#include <string.h> 7//#include <algorithm> 8#define aaa cout<<233<<endl; 9#define endl '\n' 10#define pb push_back 11using namespace std; 12typedef long long ll; 13typedef unsigned long long ull; 14typedef pair<int, int> pii; 15const int inf = 0x3f3f3f3f;//1061109567 16const ll linf = 0x3f3f3f3f3f3f3f; 17const double eps = 1e-6; 18const double pi = 3.14159265358979; 19const int maxn = 1e6 + 5; 20const int maxm = 2e5 + 5; 21const ll mod = 1e9 + 7; 22struct edge 23{ 24 int v, w; 25 edge(int _v, int _w):v(_v), w(_w){} 26}; 27vector<edge> e[maxn]; 28void addedge(int u, int v, int w) 29{ 30 e[u].push_back(edge(v, w)); 31} 32bool vis[maxn]; 33int cnt[maxn], dis[maxn], sta[maxn]; 34bool spfa(int s, int n) 35{ 36 for(int i = 0; i <= n; ++i)vis[i] = false; 37 for(int i = 0; i <= n; ++i)cnt[i] = 0; 38 for(int i = 0; i <= n; ++i)dis[i] = inf; 39 vis[s] = true; 40 cnt[s] = 1; 41 dis[s] = 0; 42 int top = -1; 43 sta[++top] = s; 44 while(~top) 45 { 46 int u = sta[top--]; 47 vis[u] = false; 48 for(int i = 0; i < e[u].size(); ++i) 49 { 50 int v = e[u][i].v; 51 int w = e[u][i].w; 52 if(dis[v] > dis[u] + w) 53 { 54 dis[v] = dis[u] + w; 55 if(!vis[v]) 56 { 57 vis[v] = true; 58 sta[++top] = v; 59 if(++cnt[v] > n)return false; 60 } 61 } 62 } 63 } 64 return true; 65} 66char s[1005][1005]; 67int main() 68{ 69// freopen("233.in" , "r" , stdin); 70// freopen("233.out" , "w" , stdout); 71// ios_base::sync_with_stdio(0); 72// cin.tie(0);cout.tie(0); 73 int n, m; scanf("%d%d", &n, &m); 74 for(int i = 1; i <= n; ++i)scanf("%s", s[i] + 1); 75 for(int i = 1; i <= n; ++i) 76 { 77 for(int j = 1; j <= m; ++j) 78 { 79 if(s[i][j] == '>') 80 addedge(i, j + n, -1); 81 else if(s[i][j] == '<') 82 addedge(j + n, i, -1); 83 else 84 { 85 addedge(i, j + n, 0); 86 addedge(j + n, i, 0); 87 } 88 } 89 } 90 for(int i = 1; i <= n + m; ++i) 91 addedge(0, i, 1); 92 if(spfa(0, n + m)) 93 { 94 printf("Yes\n"); 95 int k = *min_element(dis + 1, dis + 1 + n + m); 96 for(int i = 1; i <= n; ++i) 97 printf("%d ", dis[i] - k + 1); 98 printf("\n"); 99 for(int i = 1 + n; i <= n + m; ++i) 100 printf("%d ", dis[i] - k + 1); 101 printf("\n"); 102 } 103 else 104 printf("No\n"); 105 return 0; 106}
估计这一段时间里是不会在做差分约束的题了，，，不过正好复习一遍最短路的写法，，，
这貌似是写的最长的一篇博客了，，，30多K，，，，，233