UVA11090 Going in Cycle （二分+判负环）

二分法+spfa判负环。如果存在一个环sum(w)<k*x，i=0,1,2...,k，那么每条边减去x以后会形成负环。因此可用spfa来判负环。

一般spfa判负环dfs最快，用stack次之，queue最慢，因为一个负环中被更新的点是连续的。

一开始不知到图的连通情况，所以把所有点都入栈更新。

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

struct Edge

{

    int v,nxt;

    double w;

};

vector<Edge> edges;

int head[maxn];

#define PB push_back

void addEdge(int u,int v,double w)

{

    edges.PB({v,head[u],w});

    head[u] = edges.size()-;

}

bool vis[maxn];

double d[maxn];

int cnt[maxn];

bool spfa(int n)

{

    stack<int>S;

    memset(vis,,sizeof(vis));

    memset(cnt,,sizeof(cnt));

    for(int i = ; i < n; i++) { vis[i] = true; d[i] = .; S.push(i); }

    while(S.size()){

        int u = S.top(); S.pop();

        vis[u] = false;

        for(int i = head[u]; ~i; i = edges[i].nxt){

            Edge &e = edges[i];

            if(d[e.v]>d[u]+e.w){

                d[e.v] = d[u]+e.w;

                if(!vis[e.v]){

                    S.push(e.v); vis[e.v] = true;

                    if(++cnt[e.v] > n) return true;

                }

            }

        }

    }

    return false;

}

bool P(double x,int n)

{

    for(int i = ; i < (int)edges.size(); i++) edges[i].w -= x;

    bool ret = spfa(n);

    for(int i = ; i < (int)edges.size(); i++) edges[i].w += x;

    return ret;

}

void init()

{

    memset(head,-,sizeof(head));

    edges.clear();

}

const double eps = 1e-;

int main()

{

    //freopen("in.txt","r",stdin);

    int T;cin>>T;

    int kas = ;

    while(T--){

        init();

        int n,m; scanf("%d%d",&n,&m);

        double l = , r = ;

        while(m--){

            int u,v; double w; scanf("%d%d%lf",&u,&v,&w);

            addEdge(u-,v-,w);

            r = max(r,w);

        }

        printf("Case #%d: ",++kas);

        if(!P(r+,n)) { puts("No cycle found."); continue; }

        for(double mid; r-l>eps; P(mid,n)?r=mid:l=mid) mid = l+(r-l)/;

        printf("%.2lf\n",l);

    }

    return ;

}

dfs+判负环

bool vis[maxn];

double d[maxn];

bool dfs(int u)

{

    vis[u] = true;

    for(int i = head[u]; ~i ; i = edges[i].nxt){

        Edge &e = edges[i];

        if(d[e.v] > d[u]+e.w){

            d[e.v] = d[u]+e.w;

            if(!vis[e.v]){

                if(dfs(e.v)) return true;

            }else  return true;

        }

    }

    vis[u] = false;

    return false;

}

调用

for(int u = ; u < n; u++){

        if(dfs(u)) { ret = true; break; }

    }