ACM差分约束笔记
https://www.cnblogs.com/31415926535x/p/10463112.html
很早之前学最短路的时候就看了一眼差分约束，，当时以为这种问题不怎么会出现，，而且当时为了只为了学最短路，，所以就没有怎么做题，，知道是什么，但是不会建图使用，，
然后上一次做cf就碰到了，，虽然那道题不只是差分约束能解决还卡时间，，但是万一以后还出现这种题，，只是知道是这个类型的题却不知道如何下手也相当于是不会啊，，所以抽时间重新看了看这块的内容，，做几道题，，顺便背一背最短路的板子，，好久敲最短路的板子都已经忘记了，，
感觉这一块的东西最主要的是建图吧，，很多这样的题的解法都不止一种，，差分约束只是其中一种，，因为使用spfa实现的，，所以也很容易被卡，，
概念
这里的东西我是先参考这篇博客的还有这里
因为之前看过差分约束，，还有印象，，所以上手很快，，纯理论性东西算法导论等等的地方讲的很详细，，
首先差分约束主要是解决 不等式组的求解，，其中这些不等式组的特征是 \(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])，，所以对每一个点加一（向右偏移一个位置），，，最后求最长路就行了，，，
代码
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <queue>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
int v;
int cost;
edge(int _v = 0, int _cost = 0):v(_v), cost(_cost){}
};
vector<edge> e[maxn];
void addedge(int u, int v, int w)
{
e[u].pb(edge(v, w));
}
bool vis[maxn];
int cnt[maxn];
int dis[maxn];
bool spfa(int s, int n)
{
memset(vis, false, sizeof vis);
memset(cnt, 0, sizeof cnt);
cnt[s] = 1;
for(int i = 1; i <= n; ++i)dis[i] = -inf;
vis[s] = true;
dis[s] = 0;
queue<int> q;
while(!q.empty())q.pop();
q.push(s);
while(!q.empty())
{
int u = q.front();q.pop();
vis[u] = false;
for(int i = 0; i < e[u].size(); ++i)
{
int v = e[u][i].v;
if(dis[v] < dis[u] + e[u][i].cost)
{
dis[v] = dis[u] + e[u][i].cost;
if(!vis[v])
{
vis[v] = true;
q.push(v);
if(++cnt[v] > n)return false;
}
}
}
}
return true;
}
int main()
{
// freopen("233.in" , "r" , stdin);
// freopen("233.out" , "w" , stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int n;scanf("%d", &n);
int mi = inf, mx = 0, u, v, w;
for(int i = 1; i <= n; ++i)
{
scanf("%d%d%d", &u, &v, &w);
addedge(u, v + 1, w);
mi = min(mi, u);
mx = max(mx, v);
}
++mx;
for(int i = mi; i <= mx; ++i)
{
addedge(i, i + 1, 0);
addedge(i + 1, i, -1);
}
spfa(mi, mx);
printf("%d\n", dis[mx]);
return 0;
}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，，，
代码
//hdu
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
int to, next, w;
}edge[maxn];
int head[maxn], tot;
void addedge(int u, int v, int w)
{
edge[tot].to = v; edge[tot].next = head[u]; edge[tot].w = w; head[u] = tot++;
}
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
bool vis[maxn];
int dis[maxn], cnt[maxn];
bool spfa(int s, int n)
{
memset(vis, false, sizeof vis);
memset(cnt, 0, sizeof cnt);
for(int i = 0; i <= n; ++i)dis[i] = -inf;
vis[s] = true;
dis[s] = 0;
cnt[s] = 1;
queue<int> q;
while(!q.empty())q.pop();
q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
vis[u] = false;
//if(u == 24 && dis[u] > m)return 0;
for(int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
int w = edge[i].w;
if(dis[v] < dis[u] + w)
{
dis[v] = dis[u] + w;
if(!vis[v])
{
vis[v] = true;
q.push(v);
if(++cnt[v] > n)return false;
}
}
}
}
return true;
}
int r[30], a[maxn];
map<int, int> mp;
int check(int m)
{
init();
for(int i = 0; i <= 23; ++i)
{
addedge(i, i + 1, 0);
addedge(i + 1, i, -mp[i]);
}
for(int i = 7; i <= 23; ++i)
addedge(i - 8 + 1, i + 1, r[i]);
for(int i = 0; i < 7; ++i)
addedge(i + 16 + 1, i + 1, r[i] - m);
addedge(0, 24, m);
addedge(24, 0, -m);
if(spfa(0, 30))
return dis[24];
else
return 0;
}
int main()
{
// freopen("233.in" , "r" , stdin);
// freopen("233.out" , "w" , stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int t;scanf("%d", &t);
while(t--)
{
for(int i = 0; i <= 23; ++i)scanf("%d", &r[i]);
int n;scanf("%d", &n);
for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i)++mp[a[i]];
int l = 0, r = n + 1;
int ans = 0;
//for(int i = 1; i <= n; ++i)cout << check(i) << endl;return 0 ;
while(l + 1 < r)
{
int m = (l + r) >> 1;
int flag = check(m);
//cout << l << r << m << flag << endl;
if(m == flag)
{
r = m;
ans = m;
}
else
l = m;
}
if(l >= n)
printf("No Solution\n");
else
printf("%d\n", ans);
}
return 0;
}
//1
//1 0 3 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
//5
//0
//23
//22
//1
//10hdu-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，，据说快一些，，大概是队列时间的三分之一左右，，
普通的队列实现
//hdu
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
int to, next, w;
}edge[maxn];
int head[maxn], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v, int w)
{
edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++;
}
bool vis[maxn];
int dis[maxn], cnt[maxn];
bool spfa(int s, int n)
{
for(int i = 0; i <= n; ++i)vis[i] = false;
for(int i = 0; i <= n; ++i)cnt[i] = 0;
for(int i = 0; i <= n; ++i)dis[i] = inf;
vis[s] = true;
cnt[s] = 1;
dis[s] = 0;
queue<int> q;
while(!q.empty())q.pop();
q.push(s);
while(!q.empty())
{
int u = q.front();q.pop();
vis[u] = false;
for(int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
int w = edge[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if(!vis[v])
{
vis[v] = true;
q.push(v);
if(++cnt[v] > n)return false;
}
}
}
}
return true;
}
struct node
{
int h, id;
const bool operator<(const node &r)const
{
return h < r.h;
}
}node[maxn];
int main()
{
// freopen("233.in" , "r" , stdin);
// freopen("233.out" , "w" , stdout);
int t;scanf("%d", &t);
for(int ca = 1; ca <= t; ++ca)
{
int n, d;
scanf("%d%d", &n, &d);
for(int i = 1; i <= n; ++i)
{
node[i].id = i;
scanf("%d", &node[i].h);
}
sort(node + 1, node + 1 + n);
init();
bool flag = true;
for(int i = 1; i <= n - 1 && flag; ++i)
{
addedge(i + 1, i, -1);
int u = min(node[i].id, node[i + 1].id);
int v = max(node[i].id, node[i + 1].id);
if(u > v)flag = false;
addedge(u, v, d);
}
printf("Case %d: ", ca);
int s = min(node[1].id, node[n].id);
int t = max(node[1].id, node[n].id);
if(!flag || !spfa(s, n))printf("-1\n");
else printf("%d\n", dis[t]);
}
return 0;
}队列实现
//hdu
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
int to, next, w;
}edge[maxn];
int head[maxn], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v, int w)
{
edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++;
}
bool vis[maxn];
int dis[maxn], cnt[maxn];
bool spfa(int s, int n)
{
for(int i = 0; i <= n; ++i)vis[i] = false;
for(int i = 0; i <= n; ++i)cnt[i] = 0;
for(int i = 0; i <= n; ++i)dis[i] = inf;
vis[s] = true;
cnt[s] = 1;
dis[s] = 0;
queue<int> q;
while(!q.empty())q.pop();
q.push(s);
while(!q.empty())
{
int u = q.front();q.pop();
vis[u] = false;
for(int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
int w = edge[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if(!vis[v])
{
vis[v] = true;
q.push(v);
if(++cnt[v] > n)return false;
}
}
}
}
return true;
}
struct node
{
int h, id;
const bool operator<(const node &r)const
{
return h < r.h;
}
}node[maxn];
int main()
{
// freopen("233.in" , "r" , stdin);
// freopen("233.out" , "w" , stdout);
int t;scanf("%d", &t);
for(int ca = 1; ca <= t; ++ca)
{
int n, d;
scanf("%d%d", &n, &d);
for(int i = 1; i <= n; ++i)
{
node[i].id = i;
scanf("%d", &node[i].h);
}
sort(node + 1, node + 1 + n);
init();
bool flag = true;
for(int i = 1; i <= n - 1 && flag; ++i)
{
addedge(i + 1, i, -1);
int u = min(node[i].id, node[i + 1].id);
int v = max(node[i].id, node[i + 1].id);
if(u > v)flag = false;
addedge(u, v, d);
}
printf("Case %d: ", ca);
int s = min(node[1].id, node[n].id);
int t = max(node[1].id, node[n].id);
if(!flag || !spfa(s, n))printf("-1\n");
else printf("%d\n", dis[t]);
}
return 0;
}poj-3169-Layout
题意
一排牛，，有一些牛之间的距离不能超出d，有一些牛的距离不能小于d，，问你第一头和最后一头牛直接的距离的最大值是多少
分析
简单的差分约束，，直接建图就行了，，，(貌似不加相邻两头之间距离大于1这个条件也能过)
图有环为-1，，距离是inf为-2，其他的就是dis[n]，，
代码
//hdu
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
int to, next, w;
}edge[maxn];
int head[maxn], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v, int w)
{
edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++;
}
bool vis[maxn];
int dis[maxn], cnt[maxn], sta[maxn];
int spfa(int s, int n)
{
for(int i = 1; i <= n; ++i)vis[i] = false;
for(int i = 1; i <= n; ++i)dis[i] = inf;
for(int i = 1; i <= n; ++i)cnt[i] = 0;
vis[s] = true;
cnt[s] = 1;
dis[s] = 0;
int top = -1;
sta[++top] = s;
while(~top)
{
int u = sta[top--];
vis[u] = false;
for(int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
int w = edge[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if(!vis[v])
{
vis[v] = true;
sta[++top] = v;
if(++cnt[v] > n)return -1;
}
}
}
}
if(dis[n] == inf)return -2;
return dis[n];
}
int main()
{
// freopen("233.in" , "r" , stdin);
// freopen("233.out" , "w" , stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int n, ml, md;
scanf("%d%d%d", &n, &ml, &md);
int u, v, w;
init();
for(int i = 1; i <= ml; ++i)
{
scanf("%d%d%d", &u, &v, &w);
if(u > v)swap(u, v);
addedge(u, v, w);
}
for(int i = 1; i <= md; ++i)
{
scanf("%d%d%d", &u, &v, &w);
if(u < v)swap(u, v);
addedge(u, v, -w);
}
// for(int i = 1; i <= n; ++i)
// addedge(i + 1, i, 0);
printf("%d\n", spfa(1, n));
return 0;
}poj-1364-King
题意
题意是一个序列的一些子序列的和与k的大小关系给你，然后问你原序列的与一个数k的大小关系是否能确定出来，，
分析
还是前缀和的思想，\(dis[i]\) 表示第一个数到第i个数的和，，那么子序列[i,j]的和就表示为 \(dis[j]-dis[i]\)，，题目又给了一些子序列和与一个数的大小关系，也就是： \(dis[j] – dis[i] < or > K_i\)，，用这个条件建图，，因为最后的图可能不连通，所以再加一个源点到所有点为0的边，，
注意，题目给的是每个子序列的起点和它的长度，，大小关系没有等于的情况，，加一减一就行了，，
代码
//hdu
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
int to, w, next;
}edge[maxn];
int head[maxn], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v, int w)
{
edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++;
}
bool vis[maxn];
int dis[maxn], cnt[maxn], sta[maxn];
bool spfa(int s, int n)
{
for(int i = 0; i <= n; ++i)vis[i] = false;
for(int i = 0; i <= n; ++i)dis[i] = inf;
for(int i = 0; i <= n; ++i)cnt[i] = 0;
vis[s] = true;
cnt[s] = 1;
dis[s] = 0;
int top = -1;
sta[++top] = s;
while(~top)
{
int u = sta[top--];
vis[u] = false;
for(int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
int w = edge[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if(!vis[v])
{
vis[v] = true;
sta[++top] = v;
if(++cnt[v] > n)return false;
}
}
}
}
return true;
}
int main()
{
// freopen("233.in" , "r" , stdin);
// freopen("233.out" , "w" , stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int n, m;
while(~scanf("%d", &n) && n)
{
scanf("%d", &m);
int u, v, d;
char s[2];
init();
for(int i = 1; i <= m; ++i)
{
scanf("%d %d %s %d", &u, &v, s, &d);
if(s[0] == 'g')
addedge(u + v, u - 1, -d - 1);
else
addedge(u - 1, u + v, d - 1);
}
for(int i = 0; i <= n; ++i)
addedge(n + 1, i, 0);
if(spfa(n + 1, n + 1))
printf("lamentable kingdom\n");
else
printf("successful conspiracy\n");
}
return 0;
}poj-2983-Is the Information Reliable?
题意
n个站点排成一排，，给出一些描述信息
两个站点之间如果是P，，说明距离是确定的x
如果是V，，距离至少是1
问是否存在这样一个序列满足上面的条件
dis[i]表示第i站所在的位置距离第一个的距离，，这样两站的描述信息就能化成很多的不等式来表示，，建图判断是否存在环就行了，，注意原图可能不连通，所以加一个源点就行了，，，
按道理说栈实现spfa应该比队列实现的快一些，，但是这道题用栈实现t了（不止我一个人），，emmm迷一遍的操作，，队列可过，，
//hdu
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
int to, next, w;
}edge[maxn];
int head[maxn], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v, int w)
{
edge[tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot++;
}
bool vis[maxn];
int dis[maxn], cnt[maxn], sta[maxn];
bool spfa(int s, int n)
{
for(int i = 0; i <= n; ++i)vis[i] = false;
for(int i = 0; i <= n; ++i)cnt[i] = 0;
for(int i = 0; i <= n; ++i)dis[i] = -inf;
vis[s] = true;
cnt[s] = 1;
dis[s] = 0;
// int top = -1;
// sta[++top] = s;
queue<int> q;
while(!q.empty())q.pop();
q.push(s);
//while(~top)
while(!q.empty())
{
// int u = sta[top--];
int u = q.front(); q.pop();
vis[u] = false;
for(int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
int w = edge[i].w;
if(dis[v] < dis[u] + w)
{
dis[v] = dis[u] + w;
if(!vis[v])
{
vis[v] = true;
//sta[++top] = v;
q.push(v);
if(++cnt[v] > n)return false;
}
}
}
}
return true;
}
int main()
{
// freopen("233.in" , "r" , stdin);
// freopen("233.out" , "w" , stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int n, m;
while(~scanf("%d%d", &n, &m))
{
init();
for(int i = 1; i <= m; ++i)
{
int u, v, w;
char pv;
w = 1;
scanf(" %c %d %d", &pv, &u, &v);
if(pv == 'P')
{
scanf("%d", &w);
addedge(v, u, -w);
}
addedge(u, v, w);
}
for(int i = 1; i <= n; ++i)
addedge(0, i, 0);
if(spfa(0, n))
printf("Reliable\n");
else
printf("Unreliable\n");
}
return 0;
}codeofeces-1131d-D. Gourmet choice
做这些差分约束的题的主要的原因就是这道cf的题，，当时比赛的时候就有人说是差分约束的题，，但是因为我只是了解这块内容，，但是实际的题目完全没有写过，，所以看到题也没有什么思路，，就放弃了，，
现在再看这道题，，感觉十分的简单，，，
题意
大概的意思就是有n+m个点，，他们直接的大小关系已知（具体大或小多少没有说），，，然后问你能不能给每一个点赋一个值使得满足所给的关系，，
分析
一种解法是用并查集缩点后跑一边拓扑排序，，最后求得的最长链就是答案，，，
用差分约束解的话就是用所给的关系直接建图就行了，，对于i->j大于就正的建一条边，小于就反着建一条边，，等于就建两条就行了，，，
因为图可能是不连通的，，所以再弄个源点，连到每个点就行了，，，
因为最后要的是每一的节点一个数，，而且尽可能小，，所以就找出dis数组里距离源点最小的那个数，，然后每一个点减去这个最小的数就是最后要赋的值了，，，
对了这题用链式前向星来建图会T，，，换邻接表就好了，，，（不是说链式前向星的效率更高吗，，，emmmm，，迷，，，就像那道用栈的spfaT掉用队列就过了一样迷，，，
代码
//cf
#include <bits/stdc++.h>
//#include <iostream>
//#include <cstdio>
//#include <cstdlib>
//#include <string.h>
//#include <algorithm>
#define aaa cout<<233<<endl;
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567
const ll linf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 2e5 + 5;
const ll mod = 1e9 + 7;
struct edge
{
int v, w;
edge(int _v, int _w):v(_v), w(_w){}
};
vector<edge> e[maxn];
void addedge(int u, int v, int w)
{
e[u].push_back(edge(v, w));
}
bool vis[maxn];
int cnt[maxn], dis[maxn], sta[maxn];
bool spfa(int s, int n)
{
for(int i = 0; i <= n; ++i)vis[i] = false;
for(int i = 0; i <= n; ++i)cnt[i] = 0;
for(int i = 0; i <= n; ++i)dis[i] = inf;
vis[s] = true;
cnt[s] = 1;
dis[s] = 0;
int top = -1;
sta[++top] = s;
while(~top)
{
int u = sta[top--];
vis[u] = false;
for(int i = 0; i < e[u].size(); ++i)
{
int v = e[u][i].v;
int w = e[u][i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if(!vis[v])
{
vis[v] = true;
sta[++top] = v;
if(++cnt[v] > n)return false;
}
}
}
}
return true;
}
char s[1005][1005];
int main()
{
// freopen("233.in" , "r" , stdin);
// freopen("233.out" , "w" , stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)scanf("%s", s[i] + 1);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(s[i][j] == '>')
addedge(i, j + n, -1);
else if(s[i][j] == '<')
addedge(j + n, i, -1);
else
{
addedge(i, j + n, 0);
addedge(j + n, i, 0);
}
}
}
for(int i = 1; i <= n + m; ++i)
addedge(0, i, 1);
if(spfa(0, n + m))
{
printf("Yes\n");
int k = *min_element(dis + 1, dis + 1 + n + m);
for(int i = 1; i <= n; ++i)
printf("%d ", dis[i] - k + 1);
printf("\n");
for(int i = 1 + n; i <= n + m; ++i)
printf("%d ", dis[i] - k + 1);
printf("\n");
}
else
printf("No\n");
return 0;
}估计这一段时间里是不会在做差分约束的题了，，，不过正好复习一遍最短路的写法，，，
这貌似是写的最长的一篇博客了，，，30多K，，，，，233
版权声明：本文为31415926535x原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。