UVA 11090 Going in Cycle!!(二分 + spfa) - c++编程基础

TOP

UVA 11090 Going in Cycle!!(二分 + spfa)

2014-11-23 20:00:45 来源: 作者: 【大中小】浏览:7次

给定一个n个点m条边的有向正权边图，求平均值最小的回路。

二分mid值，每条边减去mid，看是否存在负环即可。但是这题有一点需要注意。。。原图不一定强连通，所以不能用一般的spfa来判负环。要在spfa中开始阶段，每个点都要加入队列一次。确保每个强连通分量都能加进来。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FF(i, a, b) for(int i=a; i=b; i--)
#define REP(i, n) for(int i=0; i edges;
vector G[maxn];
bool inq[maxn];
double d[maxn];
int cnt[maxn];

inline void init()
{
    REP(i, n) G[i].clear(); edges.clear();
}

void add(int a, int b, double c)
{
    edges.PB((Edge){a, b, c});
    int nc = edges.size();
    G[a].PB(nc-1);
}

bool negacycle()
{
    queue q;
    CLR(inq, 0); CLR(cnt, 0);
    REP(i, n)   d[i] = INF, q.push(i);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        inq[u] = false;
        int nc = G[u].size();
        REP(i, nc)
        {
            Edge e = edges[G[u][i]];
            if(d[e.to] > d[u] + e.dist)
            {
                d[e.to] = d[u] + e.dist;
                if(!inq[e.to])
                {
                    q.push(e.to);
                    inq[e.to] = 1;
                    if(++cnt[e.to] > n) return true;
                }
            }
        }
    }
    return false;
}

bool ok(double m)
{
    int nc = edges.size();
    REP(i, nc) edges[i].dist -= m;
    bool ret = negacycle();
    REP(i, nc) edges[i].dist += m;
    return ret;
}

int main()
{
    int T;
    scanf("%d", &T);
    FF(kase, 1, T+1)
    {
        scanf("%d%d", &n, &m);
        init();
        int a, b; double c;
        double L = 0, R = 0, M;
        while(m--)
        {
            scanf("%d%d%lf", &a, &b, &c); a--; b--;
            add(a, b, c);
            R = max(R, c);
        }
        printf("Case #%d: ", kase);
        if(!ok(R + 1))
        {
            puts("No cycle found.");
            continue;
        }
        while(R - L > 1e-3)
        {
            M = (L + R) / 2;
            if(ok(M)) R = M;
            else L = M;
        }
        printf("%.2lf\n", R);
    }
    return 0;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 2886	下一篇：poj-2186-Popular Cows-缩点

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: