第三章图论 No.6负环之01分数规划与特殊建图方式

文章目录

- - 裸题：904. 虫洞
  - 01分数规划：361. 观光奶牛
  - 特殊建图与01分数规划+trick：1165. 单词环

裸题：904. 虫洞

904. 虫洞 - AcWing题库

// 虫洞是负权且单向边，道路是正权且双向边，题目较裸，判断有无负环即可
#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 6010;
int h[N], e[M], ne[M], w[M], idx;
int n, m, k;
int dis[N], cnt[N];
int q[N];
bool st[N];

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

bool spfa()
{
    int tt = 0, hh = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(dis, 0, sizeof(dis));
    memset(st, 0, sizeof(st));
    for (int i = 1; i <= n; ++ i ) st[i] = true, q[tt ++ ] = i;
    while (hh != tt)
    {
        int x = q[hh ++ ];
        if (hh == N) hh = 0;
        st[x] = false;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (dis[y] > dis[x] + w[i])
            {
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n) return true;
                dis[y] = dis[x] + w[i];
                if (!st[y]) 
                {
                    st[y] = true;
                    q[tt ++ ] = y;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        memset(h, -1, sizeof(h));
        idx = 0;
        scanf("%d%d%d", &n, &m, &k);
        int x, y, d;
        for (int i = 0; i < m; ++ i )
        {
            scanf("%d%d%d", &x, &y, &d);
            add(x, y, d), add(y, x, d);
        }
        for (int i = 0; i < k; ++ i )
        {
            scanf("%d%d%d", &x, &y, &d);
            add(x, y, -d);
        }
        if (spfa()) puts("YES");
        else puts("NO");
    }
    return 0;
}

这个==真的服，调半天，还有，邻接表的大小又设置错了

01分数规划：361. 观光奶牛

361. 观光奶牛 - AcWing题库

在图论问题中，所有形如：某个部分之和除以某个部分之和最大的问题，被称为01分数规划，通常使用二分解决这类问题
根据题意，这道题的答案范围在 $(0, 1000]$ 中，我们需要二分这个区间找到答案
若点权之和/边权之和大于等于mid，则说明答案在 $[mi d, r]$ 之间
反之，点权之和/边权小于mid，则说明答案在 $[l, mi d]$ 之间
根据这个二段性，我们能二分出ans，使得边权之和/边权之和的最大值 = ans

现在的问题是check如何实现？
整理不等式，如下图：

一个常用的技巧：若图中的环既有点权又有边权，那么可以将点权加到出边或者入边上
那么不等式的求和可以提到外面，结合这个技巧，将点权和边权结合
若一条边由x->y，权值为w，那么将其权值设置为 $f_x-mid*w$ ， $f_x$ 为x的点权
问题就转换成了图中是否存在一个正环？
求正环只要修改三角不等式即可：dis[y] < dis[x] + w[i]

总结下：check判断图中是否存在一个环，其点权之和/边权之和大于等于mid，转换成图中是否存在一个正环（或权值和为0的环），若存在，则l = mid，否则r = mid，

思考题目的二段性
根据不等式重置边/点权
根据不等式判断题目的具体问题：负环/最小生成树/最短路

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010, M = 5010;
int h[N], e[M], ne[M], w[M], idx;
int f[N];
double dis[N];
int cnt[N]; bool st[N];
int q[N];

int n, m;

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

bool check(double mid)
{
    memset(dis, 0, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    int tt = 0, hh = 0;
    
    for (int i = 1; i <= n; ++ i ) st[i] = true, q[tt ++ ] = i;
    while (hh != tt)
    {
        int x = q[hh ++ ];
        if (hh == N) hh = 0;
        st[x] = false;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (dis[y] <= dis[x] + f[x] - mid * w[i])
            {
                dis[y] = dis[x] + f[x] - mid * w[i];
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n) return true;
                if(!st[y])
                {
                    st[y] = true;
                    q[tt ++ ] = y;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i ) scanf("%d", &f[i]);
    int x, y, d;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d%d", &x, &y, &d);
        add(x, y, d);
    }
    
    double l = 0, r = 1000;
    while (r - l > 1e-4)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    
    printf("%.2lf\n", r);
    return 0;
}

debug：点权需要从数组1号下标开始读取

特殊建图与01分数规划+trick：1165. 单词环

1165. 单词环 - AcWing题库

估算一下这题的数据量，如果按照题意建图，不仅爆空间还会爆时间，所以这题需要考虑其他建图方式

题目给定的建图方式是：单词为点，若两单词能相连，那么边的权值为1
考虑新的建图方式，以单词的前两个字符为起点，最后两个字符为终点，建立一条有向边，权值为单词的长度。这种建图方式中，点的数量最多为26 * 26，边的数量为 $10^5$

其次，题目要求环中所有单词的长度之和 / 环中的单词数量最大，显然是01分数规划
二分答案，答案的范围是 $(0, 1000]$ ，最大的答案为每个单词长度都是1000，而最小的答案0是取不到的，最小的情况应该是1，0用来表示无解
整理不等式，重新设置边权为 $w_i - 1 * mid$ ，1是由环中点的数量累加后（第二个式子）再把累加提到外面（第三个等式）得到的
check：每次根据mid判断图中是否存在正环或零环，若存在返回true，反之返回false

trick：如果spfa更新了很多次还没有结束循环，那么有极大概率可以认为图中存在环，这里设置阈值为10000（点数的十几倍），当循环次数超过该值时，直接认为图中存在环、
不过这样的trick在正规比赛中不会出现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 27 * 27, M = 1e5 + 10;
int h[N], e[M], ne[M], w[M], idx;
double dis[N];
int cnt[N], q[N];
bool st[N];

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

bool check(double mid)
{
    memset(dis, 0, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    int tt = 0, hh = 0, count = 0;
    for (int i = 0; i < N - 1; ++ i ) q[tt ++ ] = i, st[i] = true;
    while (hh != tt )
    {
        int x = q[hh ++ ];
        if (hh == N) hh = 0;
        st[x] = false;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (dis[y] <= dis[x] + w[i] - mid)
            {
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= N) return true;
                if (++ count >= 10000) return true;
                dis[y] = dis[x] + w[i] - mid;
                if (!st[y])
                {
                    st[y] = true;
                    q[tt ++ ] = y;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return false;
}

int main()
{
    int m;
    char str[1010];
    while (scanf("%d", &m), m)
    {
        memset(h, -1, sizeof(h));
        idx = 0;
        for (int i = 0; i < m; ++ i )
        {
            scanf("%s", str);
            int len = strlen(str);
            if (len >= 2)
            {
                int x = (str[0] - 'a') * 26 + str[1] - 'a';
                int y = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
                add(x, y, len);
            }
        }
        
        double l = 0, r = 1000;
        while (r - l > 1e-4)
        {
            double mid = (l + r) / 2;
            if (check(mid)) l = mid;
            else r = mid;
        }
        
        if (r < 1e-4) puts("No solution");
        else printf("%.2lf\n", r);
    }
    return 0;
}