负环
负环是指图中出现了一个边权和为负的环。出现负环意味着该图不存在最短路，即S -> T的路径上一定可以通过一直经过负环无限缩小路径长度。
负环的判断可以使用SPFA算法。SPFA算法的特点是当一个点的最短路径发生更新时才会将点放入队列，故如果图中存在负环，则使用SPFA算法会一直进行更新，此时只需判断一个阈值，当超过阈值即可判断存在负环。
设置阈值有两种方法。第一种比较稳定但较慢，第二种不稳定但从经验角度来看一般可行。此外还存在一种优化。
第一种阈值为判断每个点最短路所包含的边数。如果某一点最短路包含边数大于等于n，则说明存在负环。
第二种阈值为判断入队次数是否大于某一值，如大于四倍点数时，可以判断存在负环。
优化则是可以将队列替换为栈，则如存在负环时，每次都会取最新更新的点判断，可以拥有更快的效率。
题意：
给定一个无向图，以及一些有向负权边，问是否存在负环。
解析：
spfa找负环模板题，直接求解即可
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
struct node{
int u,v,w,next;
}a[M];
int f[N],cnt;
void add(int u,int v,int w){
a[++cnt].v = v;
a[cnt].w = w;
a[cnt].next = f[u];
f[u] = cnt;
}
int dis[N],Count[N],st[N];
int n,m,k;
bool spfa(){
memset(dis,0,sizeof dis);
memset(Count,0,sizeof Count);
memset(st,0,sizeof st);
queue<int> q;
for(int i = 1;i<=n;i++){
q.push(i);
st[i] = 1;
}
while(!q.empty()){
int u = q.front();
q.pop();
st[u] = 0;
for(int i =f[u];i;i = a[i].next){
int v = a[i].v,w = a[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
Count[v] = Count[u] + 1;
if(Count[v] >= n) return true;
if(!st[v]){
st[v] = 1;
q.push(v);
}
}
}
}
return false;
}
int main() {
int t;
cin>>t;
while(t--){
memset(f,0,sizeof f);
cnt = 0;
cin>>n>>m>>k;
for(int i = 1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(int i = 1;i<=k;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,-w);
}
if(spfa()) puts("YES");
else puts("NO");
}
return 0;
}
|
01分数规划
这个知识点是在学习负环时学到的，但实际它并不只能在负环里存在。该方法通常用于求一分数的极值，如题目给出每个物品的A值和B值，问如何选择物品使得∑inBi∑inAi最大。
跟二分思想相似，我们选择某一值X，寻找给定物品里是否存在∑inBi∑inAi大于等于X，即∑inBi∑inAi>=X，而该式子又等价于∑inAi−X∗∑inBi>=0。故可以使用二分查找枚举X，根据是否存在物品的集合满足上式判断是否最优。
由于该式子的性质，使得它可以在很多问题中出现，如普通的集合，或图论中都可以出现。下面这道例题就是结合了图论和01分数规划还有负环的一道模板题。
题意：
给定一张 L 个点、P 条边的有向图，每个点都有一个权值 f[i]，每条边都有一个权值 t[i]。
求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。
解析：
求一个环上∑f[i]∑t[i]的最大值，设值X，则原式可转换为∑t[i]−X∗∑f[i]>=0。同时由于环上点与边的数量相等，可以将一个点的权值放在它的出边上，即该出边权值为t[i]+f[i]。运用这种思想，讲上式取反设为边权，即每条边的边权为f[i]∗X−t[i]，即可通过spfa求负环的方式找到是否存在这样的一个环，并且可以通过二分查找不断优化答案直到求出最大值。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-7;
struct node{
int u,v,w,next;
}a[M];
int f[N],cnt;
void add(int u,int v,int w){
a[++cnt].v = v;
a[cnt].w = w;
a[cnt].next = f[u];
f[u] = cnt;
}
int Count[N],st[N];
double dis[N];
int val[N];
int n,m,k;
bool spfa(double mid){
for(int i = 1;i<=n;i++) dis[i] = 0;
memset(Count,0,sizeof Count);
memset(st,0,sizeof st);
queue<int> q;
for(int i = 1;i<=n;i++){
q.push(i);
st[i] = 1;
}
while(!q.empty()){
int u = q.front();
q.pop();
st[u] = 0;
for(int i =f[u];i;i = a[i].next){
int v = a[i].v;
double w = a[i].w*mid-val[u];
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
Count[v] = Count[u] + 1;
if(Count[v] >= n) return true;
if(!st[v]){
st[v] = 1;
q.push(v);
}
}
}
}
return false;
}
int main() {
cin>>n>>m;
for(int i = 1;i<=n;i++){
scanf("%d",&val[i]);
}
for(int i = 1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
double l = 0,r = 1000;
double ans = 0;
while(fabs(l-r)>eps){
double mid = (l+r)/2.0;
if(spfa(mid)){
ans = mid;
l = mid;
}else{
r = mid;
}
}
printf("%.2f\n",ans);
return 0;
}
|
差分约束
差分约束可以解决一个由n个变量组成的一元不等式组的问题，其中每个不等式为两个变量做差组成，如xj−xi≤ck。
我们可以对上式进行变形，得到xj≤xi+ck这样如果我们以xi−xj权值为c进行建图，则如果我们在这样的图上跑一遍最短路，对于每条边的任意两点xi,xj必然有dis[xj]≤dis[xi]+ck。这是因为在最短路中进行更新时，每条边如果满足dis[xj]>dis[xi]+ck则必然会被更新。
