跳到主要内容

SPFA求负环

AcWing 904. 虫洞​

题目​

https://www.acwing.com/problem/content/906/ 虫洞非常奇特，它可以看作是一条 单向 路径，通过它可以使你回到过去的某个时刻（相对于你进入虫洞之前）。 农夫约翰的每个农场中包含 N 片田地，M 条路径（双向）以及 W 个虫洞。现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。他希望能够看到出发之前的自己。请你判断一下约翰能否做到这一点。 下面我们将给你提供约翰拥有的农场数量 F，以及每个农场的完整信息。 已知走过任何一条路径所花费的时间都不超过 10000 秒，任何虫洞将他带回的时间都不会超过 10000 秒。

思路​

负环：一个有向图/无向图 中环路的边权和<0; 求负环算法：SPFA

  • 基于抽屉原理，如果一条正在搜索的最短路径上的点的个数大于总共点的个数，则说明路径上一定有至少重复的两个点，走了回头路。又因为满足最短路径的性质，所以一定存在负环。
  • spfa，记录每个点的cnt，当cnt >= 点的个数说明有负环。
  • 找负环不需要初始化dist数组，因为只要有负环，某个点的距离就能被一直更新下降，cnt总会大于点的个数。
  • 如果建立了虚拟源点，则总共的点数n要 + 1。但cnt的判断要看初始化的情况。这里一次性将所有点入队后仍然只需要cnt >= n,因为虚拟源点到到j的边数 >= n + 1，一次性入队已经扣除一条边了。但如果没有一次性全部入队则需要 cnt >= n + 1

代码​

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=510,M=5210;
int n,m1,m2;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int q[N],cnt[N];

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

bool spfa()
{
    memset(dist,0,sizeof dist);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);

    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        q[tt++]=i;
        st[i]=true;
    }

    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[j])
                {
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
    return false;
}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m1>>m2;
        memset(h,-1,sizeof h);
        idx=0;
        while(m1--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c),add(b,a,c);
        }
        while(m2--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,-c);
        }
        if(spfa()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

AcWing 361. 观光奶牛​

题目​

https://www.acwing.com/problem/content/363/ 给定一张 L 个点、P 条边的有向图，每个点都有一个权值 f[i]，每条边都有一个权值 t[i]。求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。输出这个最大值。 注意：数据保证至少存在一个环。

思路​

01分数规划问题： 本题需要求∑f(i)∑t(i)\frac{\sum f(i)}{\sum t(i)}的最大值，这个答案具有二分的性质，即：存在标准>=k的环和不存在标准>=k的环。我们需要二分到他的最大值，利用二分出的mid，有∑f(i)∑t(i)>mid\frac{\sum f(i)}{\sum t(i)}>mid,对公式进行变形操作：∑f(i)>∑t(i)⋅mid\sum f(i) >\sum t(i)·mid--->∑f（i）−∑t(i)⋅mid>0\sum f（i）-\sum t(i)·mid>0-->∑(f(i)−t(i)⋅mid)>0\sum (f(i)-t(i)·mid)>0 满足要求的mid，就是要满足图中存在一个环∑(f(i)−t(i)⋅mid)>0\sum (f(i)-t(i)·mid)>0

SPFA算法在求最短路的时候可以把点权和边权看做一个整体边权一起更新

本题利用SPFA的性质，把边权t(i)t(i)换成f(i)−t(i)⋅midf(i)-t(i)·mid来存储，把每个点存入出边中，原问题可以变成一个图中是否存在正环的问题。

结果要求保留两位小数，一般来说二分里面写 r-l>1e-4 ,相差两位，以此类推

代码​

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=1010,M=5010;
int n,m;
int wf[N];
int h[N],e[M],ne[M],w[M],idx;
double dist[N];
int q[N],cnt[N];
bool st[N];

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

bool check(double mid)
{
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        q[tt++]=i;
        st[i]=true;
    }
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+wf[t]-mid*w[i])
            {
                dist[j]=dist[t]+wf[t]-mid*w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                
                if(!st[j])
                {
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
    return false;
}   

int main()
{   
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) cin>>wf[i];
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    double l=0,r=1010;
    while(r-l>1e-4)
    {
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf",l);
    return 0;

}

AcWing 1165. 单词环​

题目​

https://www.acwing.com/problem/content/1167/ 我们有 n 个字符串，每个字符串都是由 a∼z 的小写英文字母组成的。 如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。 我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。例如：

ababc
bckjaca
caahoynaab

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

思路​

建图： 如果将每个单词作为一个节点，在两个单词之间连一条边，数据最大是10^5,将会有10^10,pass. 可以考虑用一个对偶的建图方式，将单词开头和结尾的两个字符作为它两边的点，节点数就缩小到676个，边数为10^5 01分数规划问题： 题目要求 ∑lens\frac{\sum len} {s}的最大值，s表示单词个数，len表示每个单词的长度，可以使用二分来求，∑lens>mid\frac{\sum len}{s}>mid,即∑len−s⋅mid>0\sum len -s·mid>0,可以用len[i]-mid作为边权 优化： 当求最长路时,经过的点大于某一个数时,我们就可以武断地认为当前图中存在一个正环.

代码​

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N = 700, M = 100010;

int n;
int h[N], e[M], w[M], ne[M], idx;
double dist[N];
int q[N], cnt[N];
bool st[N];

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

bool check(double mid)
{
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);

    int hh = 0, tt = 0;
    for (int i = 0; i < 676; i ++ )
    {
        q[tt ++ ] = i;
        st[i] = true;
    }

    int count = 0;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i] - mid)
            {
                dist[j] = dist[t] + w[i] - mid;
                cnt[j] = cnt[t] + 1;
                if ( ++ count > 10000) return true; // 经验上的trick
                if (cnt[j] >= N) return true;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    char str[1010];
    while(cin>>n,n)
    {
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=0;i<n;i++)
        {
            cin>>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(!check(0)) cout<<"No solution"<<endl;
        else
        {
            double l=0,r=1000;
            while(r-l>1e-4)
            {
                double mid=(l+r)/2;
                if(check(mid)) l=mid;
                else r=mid;
            }
            cout<<r<<endl;
        }
    }
    return 0;
}

0%