01分数规划问题(负环) – 更新

开心！！markdown直接导入wp中的方法

其实很简单，因为wp支持html编辑，所以可以将md先转换成html再把html直接复制到wp的html编辑块中即可qwq – 很开心，之后可以在本地写好之后直接上传了~~~~开心！！！

负环

Contents

负环
SPFA求解负环问题
题目

负环

负环顾名思义就是对于一个图而言，存在着一个环的权值之和是负数

SPFA求解负环问题

求解负环问题就是判断一个图中是否存在负环
求解负环问题的常见的两种方法(基于SPFA)：

统计每个点入队的次数，如果某个入队 $n$ 次，则说明存在负环
统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于 $n$ , 则也说明存在环

常用的是第2种方法

时间复杂度：
$spfa:O(m)$
那么综合起来的时间复杂度最坏的情况： $O(n * m)$

这个时间复杂度是比较高的，但是大多数题目都不会达到这个复杂度，如果发现一直 $T$ 的话, 可以试一下这个 $Track$ (单词不知道写的对不对)的方法：

设定一个阈值，如果某个点入队的次数超过某个阈值的话，那么就认为是存在负环，显然是存在很简单的反例的，但是大多数都是负环的，都是正确的，如果经常 $T$ 的话，可以尝试的使用这样的方法，后面的一道题目也是需要用到这个
一般阈值设置为 $2 * n$

在负环中有很经典的题目：01分数规划
后面会讲到这个题目

题目

904. 虫洞

农夫约翰在巡视他的众多农场时，发现了很多令人惊叹的虫洞。

虫洞非常奇特，它可以看作是一条单向路径，通过它可以使你回到过去的某个时刻（相对于你进入虫洞之前）。

农夫约翰的每个农场中包含 $N$ 片田地， $M$ 条路径（双向）以及 $W$ 个虫洞。

现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。

他希望能够看到出发之前的自己。

请你判断一下约翰能否做到这一点。

下面我们将给你提供约翰拥有的农场数量 $F$ ，以及每个农场的完整信息。

已知走过任何一条路径所花费的时间都不超过 $10000$ 秒，任何虫洞将他带回的时间都不会超过 $10000$ 秒。

输入格式
第一行包含整数F，表示约翰共有 $F$ 个农场。

对于每个农场，第一行包含三个整数 $N，M，W$

接下来M行，每行包含三个整数 $S，E，T$ , 表示田地 $S$ 和 $E$ 之间存在一条路径，经过这条路径所花的时间为 $T$

再接下来 $W$ 行，每行包含三个整数 $S, E, T$ , 表示存在一条从田地 $S$ 走到田地 $E$ 的虫洞，走过这条虫洞，可以回到 $T$ 秒之间。

输出格式
输出共 $F$ 行，每行输出一个结果。

如果约翰能够在出发时刻之前回到出发地，则输出 $“YES”$ , 否则输出 $“NO”$

数据范围
$1≤F≤5$
$1≤N≤500$
$1≤M≤2500$
$1≤W≤200$
$1≤T≤10000$
$1≤S,E≤N$

输入样例

输出样例

NO
YES

分析：
很裸的一道负环题目，不过有个点：

对于求解负环问题而言，不需要初始化 $d$ 数组，初始化了也无所谓，对于任意值都是正确的，因为负环是无穷问题，是 $-inf$ 的问题

AC代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 6;

int t;
int n;
int d[maxn];
bool st[maxn];
int cnt[maxn];
queue<int > q;

int h[maxn], e[maxn], w[maxn], ne[maxn], idx;

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa(){
    memset(d, 0x3f, sizeof d);
    memset(cnt, 0, sizeof cnt);
    for(int i = 1;i <= n;++i) q.push(i);
    while(q.size()){
        int x = q.front(); q.pop();
        st[x] = false;
        for(int i = h[x];~i;i = ne[i]){
            int y = e[i];
            if(d[x] + w[i] < d[y]){
                d[y] = d[x] + w[i];
                cnt[y] = cnt[x] + 1;
                if(cnt[y] >= n) return true;
                if(!st[y]){
                    q.push(y);
                    st[y] = true;
                }
            }
        }
    }
    return false;
}

int main(){
    sd(t);
    while(--t >= 0){
        int m1, m2;
        memset(h, -1, sizeof h);
        sd(n), sd(m1), sd(m2);
        for(int i = 0;i < m1;++i){
            int a, b, c; sd(a), sd(b), sd(c);
            add(a, b, c), add(b, a, c);
        }
        for(int i = 0;i < m2;++i){
            int a, b, c; sd(a), sd(b), sd(c);
            add(a, b, -c);
        }
        if(spfa()) puts("YES");
        else puts("NO");
    }
    
    return 0;
}

361. 观光奶牛

给定一张L个点、P条边的有向图，每个点都有一个权值 $f[i]$ ，每条边都有一个权值 $t[i]$ 。

求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意：数据保证至少存在一个环。

输入格式
第一行包含两个整数 $L$ 和 $P$

接下来 $L$ 行每行一个整数，表示 $f[i]$

再接下来 $P$ 行，每行三个整数 $a, b, t[i]$ , 表示点a和b之间存在一条边，边的权值为 $t[i]$

输出格式
输出一个数表示结果，保留两位小数。

数据范围
$2≤L≤1000$
$2≤P≤5000$
$1≤f[i],t[i]≤1000$

输入样例

输出样例

6.00

分析：
这个就是经典的01分数规划问题，01分数规划指的是图中的某些信息之间的比值，求和这些比值的有关一些问题

这个题目中求解的是：点权值和比上边权值和
$\frac{\sum f[i]}{\sum t[i]}$ 最大为多少

那么求解最大问题，可以想到二分，那么现在问题转换成对于当前答案 $mid$ 而言，如何判断其是否满足条件：即存在某个环满足上面的条件，将上面的式子变换一些：

$\frac{\sum f[i]}{\sum t[i]} > mid$
$\rightarrow \sum f[i] > mid * \sum t[i]$
$\rightarrow \sum (f[i] – mid * t[i]) > 0$

即等价于询问图中是否存在正环，正环和负环相同，求解的时候，可以将边变成相反数或者直接按照求解最长路径的方法来求解

那么还有一个问题，上面的式子是不同的权值，一个是点的权值，另外一个是边的权值，不方便处理，那么有一个很常用的技巧，就是将点的权值记录在边中，记录在出边或者入边都是可以的，那么就可以直接将边的权值变成上面的那个括号里面的值，直接求是否存在正环即可

AC代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 6;

int n, m;
double d[maxn];
int cnt[maxn];
bool st[maxn];
int f[maxn];
queue<int > q;

int h[maxn], e[maxn], w[maxn], ne[maxn], idx;

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool judge(double u){
    memset(cnt, 0, sizeof cnt);
    memset(d, -0x3f, sizeof d);
    for(int i = 1;i <= n;++i) q.push(i);
    while(q.size()){
        int x = q.front(); q.pop();
        // cout << x << endl;
        st[x] = false;
        for(int i = h[x];~i;i = ne[i]){
            int y = e[i];
            double W = static_cast<double >(f[x]) - u * w[i];
            if(d[x] + W > d[y]){
                d[y] = d[x] + W;
                cnt[y] = cnt[x] + 1;
                if(cnt[y] >= n) return true;
                if(!st[y]){
                    q.push(y);
                    st[y] = true;
                }
            }
        }
    }
    return false;
}

int main(){
    memset(h, -1, sizeof h);
    sd(n), sd(m);
    for(int i = 1;i <= n;++i) sd(f[i]);
    for(int i = 0;i < m;++i){
        int a, b, c; sd(a), sd(b), sd(c);
        add(a, b, c);
    }
    double l = 0.0, r = 1000;
    while(r - l > 1e-4){
        double mid = (l + r) / 2;
        if(judge(mid)) l = mid;
        else r = mid;
    }
    printf("%.2f\n", r);

    return 0;
}

1165. 单词环

我们有 $n$ 个字符串，每个字符串都是由 $a∼z$ 的小写英文字母组成的。

如果字符串 $A$ 的结尾两个字符刚好与字符串 $B$ 的开头两个字符相匹配，那么我们称 $A$ 与 $B$ 能够相连（注意： $A$ 能与 $B$ 相连不代表 $B$ 能与 $A$ 相连）。

我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。

如下例：

ababc
bckjaca
caahoynaab

第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 $5+7+10=22$ （重复部分算两次），总共使用了 $3$ 个串，所以平均长度是 $223≈7.33$ 。

输入格式
本题有多组数据。

每组数据的第一行，一个整数 $n$ ，表示字符串数量；

接下来 $n$ 行，每行一个长度小于等于 $1000$ 的字符串。

读入以 $n=0$ 结束。

输出格式
若不存在环串，输出 $”No solution”$ ，否则输出最长的环串的平均长度。

只要答案与标准答案的差不超过 $0.01$ ，就视为答案正确。

数据范围
$1≤n≤105$

输入样例

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

输出样例

21.66

分析：
本题的关键在于建图~
本质还是01分数规划问题

题目的意思是给定的几个字符串，其中一个的结尾的两个字符和另外一个前面开头的两个字符可以相互的组合

题目的问题是这样的组成的一个环的最大长度是什么

这个题目的解题步骤：

建立图
计算比值转换成01分数规划问题
判断是否有正环即可

这个题目最关键的就是如何建立图：

很容易出错的一种建图的方法就是：对于当前字符串，求出其能够往后面衔接的字符串，将两者之间建立一条有向边，但是细致分析的话，这样的建图方式是不合理的，因为题目数据中 $n$ 的最大值是 $1e5$ 那么就会有 $1e5$ 个节点，同时会有 $1e10$ 条边，显然是无法建立的，超时和超空间的，所以要换一种建图的方式

一种很巧妙的建图方式，也很常用，就是对于一个字符串，比如是 $abcbc$ 而言，可以建立从 $ab$ 到 $bc$ 的边，而这个边的权值就是这个字符串的长度。这样可以证明出与原问题是等价的。并且这样建立图形的话，最多就会有 $26 * 26 = 676$ 条边，很完美的建图方式

其中节点如何表示呢？比较方便的方法就是直接用两个字符按照26进制的方式来记录即可

最后发现即使按照上面的来做还是会T，这个就是上面说的问题，在求解负环的问题中是可能会出现这样的情况的，有两种处理的方法：

Trick方法：记录一个Count表示被更新的次数(d被更新的次数)，按照经验值其 $> 2 * n$ 的时候即可认为是存在负环的
将 $spfa$ 算法中的队列改为栈，在求解负环问题中会有良好的时间复杂度

AC代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 6;

int n;
int h[maxn], e[maxn], w[maxn], ne[maxn], idx;

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int cnt[maxn];
double d[maxn];
queue<int > q;
bool st[maxn];

bool judge(double mid){
    memset(cnt, 0, sizeof cnt);
    memset(st, false, sizeof st);
    while(q.size()) q.pop();
    int Count = 0;
    for(int i = 0;i <= 26 * 26;++i) q.push(i), st[i] = true;
    while(q.size()){
        int x = q.front(); q.pop();
        st[x] = false;
        for(int i = h[x];~i;i = ne[i]){
            int y = e[i];
            double W = static_cast<double >(w[i]) - mid;
            if(d[x] + W > d[y]){
                d[y] = d[x] + W;
                cnt[y] = cnt[x] + 1;
                if(++Count >= 2 * n) return true; 
                if(!st[y]){
                    q.push(y);
                    st[y] = true;
                }
            }
        }
    }
    return false;
}

int main(){
    while(sd(n), n){
        memset(h, -1, sizeof h);
        for(int i = 0;i < n;++i){
            char str[1010]; scanf("%s", str);
            int len = strlen(str);
            if(len >= 2){
                int left = (str[0] - 'a') * 26 + str[1] - 'a';
                int right = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
                add(left, right, len);
            }
        }
        if(!judge(0)) puts("No solution");
        else {
            double l = 0.0, r = 1000.0;
            while(r - l > 1e-4){
                double mid = (l + r) / 2;
                if(judge(mid)) l = mid;
                else r = mid;
            }
            printf("%lf\n", r);
        }
    }

    return 0;
}

负环

SPFA求解负环问题

题目

904. 虫洞

361. 观光奶牛

1165. 单词环

发表评论 取消回复

发表评论取消回复