spfa 判断负环的话

1.某个点出队n次，存在负环。

2.某条路径上的边数大于等于n,说明存在负环。(通常采用这种)

 

0 1 分数划分的话(通常配合二分做)

比如 题目求  ∑wf[i] /  ∑wt[i]  > mid     ==>   ∑( wf [i]  - mid * wt[i] ) > 0   ,那这样就是在求是否存在 正环。

而通常的spfa时判断存不存在负环 那怎么变呢，  第一种 可以把上面 不等式填个负号， 转化成求 负环，第二种 就是 我转变一下思路，假如存在负环，假如 当前这个点是t，它的邻接点是就 j ,dist[j]的更新条件是dist[t]+（wf [i]  - mid * wt[i]）< dist[ j ]，那么同样的假如存在正环，我们只要改变一下更新判断的条件，  dist[t]+（wf [i]  - mid * wt[i]）>dist[ j ]  ,我们就更新一下 dist[ j ] 。

 

这里其实有个trick，就是当数据很多的时候，看更新的点数已经是原来的几十倍的话，就有大概率是环，经验值。

 

题目的话就是，

AcWing 361

观光奶牛

//0 1分数规划
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010,M=5010;

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

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*wt[i])
            {
                dist[j]=dist[t]+wf[t]-mid*wt[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;
}
void add(int a,int b ,int c)
{
    e[++idx]=b,ne[idx]=h[a],h[a]=idx,wt[idx]=c;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i) scanf("%d",&wf[i]);
    
    while(m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    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",l);
    return(0);
}

 

AcWing 1165

单词环

（把一个点拆成 一条边 点数就会下降到26*26=676个，然后还要加小trick才能过）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=700,M=1e5+10;

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

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

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) //26*26=676
    {
        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(scanf("%d",&n),n)
    {
        idx=0;
        memset(h,0,sizeof h);
        for(int i=0;i<n;++i)
        {
            scanf("%s",str);
            int len=strlen(str);
            int a=(str[0] - 'a') * 26 + str[1] - 'a';
            int b=(str[len-2] - 'a') * 26 + str[len-1] - 'a';
            add(a,b,len);
        }
        if(!check(0)) puts("No solution");
        else{
            double l=0,r=1001;
            while(r-l>1e-4)
            {
                double mid=(l+r)/2;
                if(check(mid)) l=mid;
                else r=mid;
            }
            printf("%.2lf\n",l);
        }
    }
    return(0);
}