图论中的负环
图中存在一个环，它所含边的权值和是负数。常用方法基于SPFA和抽屉原理
统计每个点入队的次数，如果某个点入队n次，说明存在负环
统计当前每个点中最短路所包含的边数，如果存在某个点的边数对于等于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
| #include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 510,M=2510,INF = 0x3f3f3f3f;
int n,m,w,f;
vector<PII> mp[N];
bool st[N];
int cnt[N],dis[N];
bool spfa(){
memset(cnt,0,sizeof cnt);
memset(dis,0,sizeof dis);
memset(st,0,sizeof st);
queue<int> qu;
for (int i = 1; i <= n; i ++ ){
qu.push(i);
st[i] = true;
}
while(qu.size()){
int tp=qu.front();
qu.pop();
st[tp] = false;
for(auto nw:mp[tp]){
if(dis[nw.first] > nw.second + dis[tp]){
dis[nw.first] = nw.second + dis[tp];
cnt[nw.first] = cnt[tp] +1;
if(cnt[nw.first]>=n) return true;
if(!st[nw.first]){
qu.push(nw.first);
st[nw.first]= true;
}
}
}
}
return false;
}
int main(){
cin>>f;
while(f--){
cin>>n>>m>>w;
for(int i=0;i<=n;i++) mp[i].clear();
int a,b,c;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
mp[a].push_back({b,c});
mp[b].push_back({a,c});
}
for(int i=0;i<w;i++){
scanf("%d%d%d",&a,&b,&c);
mp[a].push_back({b,-c});
}
if(spfa()) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
|
技巧总结：在SPFA的时候，记得把所有点都放进队列（因为原图不一定连通）。另外，判断负环时dis数组不需要初始化。
题意：给定一张 L 个点、P 条边的有向图，每个点都有一个权值 f[i]，每条边都有一个权值 t[i]。求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。输出这个最大值。
思考：这类问题有一个名字：01分数规划。一般用二分答案的方法。
设一个环 $S$ 的边权为 $t_{1}, t_{2}, t_{3} \ldots$, 点权为 $f_{1}, f_{2}, f_{3} \ldots$
- 若 mid $<=a n s$, 即存在一个环 $S$ 使得 mid $<=\frac{\sum f_{i}}{\sum t_{i}}$, 变换一下: $\sum\left(\right.$ mid $\left.* t_{i}-f_{i}\right)<=0$
- 否则, 则 $m i d>a n s$
每次 check 的时候, 一条 $u$ 指向 $v$, 边权为 $w$ 的边权变为:
$w *$ mid $-f_{u}$ 。 我们只需检查这个图是否存在负环即可。
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
| #include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 1010,M=2510,INF = 0x3f3f3f3f;
double dis[N];
int cnt[N];
bool st[N];
vector<PII> mp[N];
int f[1010];
int l,p;
bool check(double mid){
queue<int> qu;
for(int i=1;i<=l;i++){
dis[i] = cnt[i] = 0;
st[i] = true;
qu.push(i);
}
while(qu.size()){
int u = qu.front();
qu.pop();
st[u] = false;
for(auto nw:mp[u]){
double w = nw.second*mid - f[u];
if(dis[u]+w < dis[nw.first]){
dis[nw.first]=dis[u]+w;
cnt[nw.first]=cnt[u]+1;
if(cnt[nw.first ]>= l) return true;
if(!st[nw.first]) qu.push(nw.first),st[nw.first]=true;
}
}
}
return false;
}
int main(){
cin>>l>>p;
for(int i=1;i<=l;i++) scanf("%d",&f[i]);
for(int i=1;i<=p;i++){
int a,b,v;
scanf("%d%d%d",&a,&b,&v);
mp[a].push_back({b,v});
}
double left=0,right=1000,ee=1e-4;
double mid=(left+right)/2;
int tt=0;
while(right-left > ee){
mid=(left+right)/2;
if(tt>50) break;
if(check(mid)){
left=mid;
}else{
right=mid;
}
}
printf("%.2lf\n", right);
return 0;
}
|
技巧总结：注意是浮点数二分，此外新图的边权在做spfa的时候边做边算就行了。
题意：我们有 n 个字符串，每个字符串都是由 a∼z 的小写英文字母组成的。
如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。
我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。
思考：这同样是一个01规划问题。考虑怎么见图呢？
如果每个字符串是一个点，如果两个字符串可以关联就连一条边，那么点数1e5，边数1e10，显然不能这样做。
注意到判断相连时只考虑2个字母，不妨将两个字母作为点，字符串作为边，连接的两个点代表它的首位两个字母。那么就有26*26个点，1e5条边了。
建完图过后，设二分的答案为mid，边权为 字符串的长度减mid，那么问题等价于找是否有负环。
做完后发现会TLE，需要加一个trick，见代码注释。
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
78
79
80
81
82
83
| #include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,double> PID;
const int N = 700,M=2510,INF = 0x3f3f3f3f;
double dis[N];
int cnt[N],cnnt;
bool st[N];
vector<PID> mp[N];
int f[1010];
int n;
bool check(double mid){
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
memset(dis, 0, sizeof dis);
cnnt=0;
queue<int> qu;
for(int i=0;i<676;i++){
qu.push(i);
}
while(qu.size()){
int tp=qu.front();
qu.pop();
st[tp] = false;
for(auto nx:mp[tp]){
int j=nx.first;
double w = nx.second-mid;
if(dis[j] < w+dis[tp]){
dis[j] =w+dis[tp];
cnt[j]=cnt[tp]+1;
cnnt++;
if(cnnt>10000) return true;
if(cnt[j]>=676) return true;
if(!st[j]){
qu.push(j);
st[j]= true;
}
}
}
}
return false;
}
int main(){
char str[1010];
while( scanf("%d",&n),n) {
for(int i=0;i<=N;i++) mp[i].clear();
for (int i = 0; i < n; i++) {
scanf("%s", str);
int len = strlen(str);
if (len >= 2)
{
int a = (str[0] - 'a') * 26 + str[1] - 'a';
int b = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
mp[a].push_back({b,len});
}
}
if (!check(0)) {
printf("No solution\n");
}else{
double l = 0, r = 1000;
while (r - l > 1e-4)
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%0.2lf\n", r);
}
}
return 0;
}
|
技巧总结：01分数规划的应用，注意全部用double
