Uva 11478 Halum操作

题目链接：http://vjudge.net/contest/143318#problem/B

题意：给定一个有向图，每条边都有一个权值。每次你可以选择一个结点v和一个整数d,把所有以v为终点的边的权值减小d,把所有以v为起点的边的权值增加d,最后让所有边的权值的最小值大于零且尽量大。

分析:

最小值尽量大，二分，最大不能超过最大边，要是最大边的话，其他边满足不了非负；

题意说的各种操作，他互不影响；也就变成了操作各边。

对于各点的操作来说：

令sum(u) 是作用于 u 上的所有 d 之和;

a—> b边的权值就是： w(a,b) +sum(a) - sum(b)>=x(答案);

对上式变形： sum(b) - sum(a) <= w(a,b) -x;

sum(b) - sum(a) 就是对这条边的操作。

这就是一个差分约束系统。

枚举这个sum(b) - sum(a) ，要是有负环，就是查分系统无解。

没有负环，说明，这个最小值还可以大一点。

#include <bits/stdc++.h>

using namespace std;

const int maxn =  + ;

struct Edge

{

    int from,to;

    double dist;

};

struct BellmanFord

{

    int n, m;

    vector<Edge> edges;

    vector<int> G[maxn];

    bool inq[maxn];

    double d[maxn];

    int p[maxn];

    int cnt[maxn];

    void init(int n)

    {

        this->n = n;

        for(int i = ; i < n; i++) G[i].clear();

        edges.clear();

    }

    void AddEdge(int from, int to, double dist)

    {

        edges.push_back((Edge)

        {

            from, to, dist

        });

        m = edges.size();

        G[from].push_back(m-);

    }

    bool negativeCycle()

    {

        queue<int> Q;

        memset(inq, , sizeof(inq));

        memset(cnt, , sizeof(cnt));

        for(int i = ; i < n; i++)

        {

            d[i] = ;

            inq[] = true;

            Q.push(i);

        }

        while(!Q.empty())

        {

            int u = Q.front();

            Q.pop();

            inq[u] = false;

            for(int i = ; i < G[u].size(); i++)

            {

                Edge& e = edges[G[u][i]];

                if(d[e.to] > d[u] + e.dist)

                {

                    d[e.to] = d[u] + e.dist;

                    p[e.to] = G[u][i];

                    if(!inq[e.to])

                    {

                        Q.push(e.to);

                        inq[e.to] = true;

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

                    }

                }

            }

        }

        return false;

    }

};

BellmanFord solver;

bool test(int x)

{

    for(int i=; i<solver.m; i++)

    {

        solver.edges[i].dist -=x;

    }

    bool ret = solver.negativeCycle();

    for(int i=; i<solver.m; i++)

    {

        solver.edges[i].dist +=x;

    }

    return !ret;

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        solver.init(n);

        int ub = ;

        for(int i=; i<m; i++)

        {

            int u,v,dist;

            scanf("%d%d%d",&u,&v,&dist);

            ub = max(ub,dist);

            u--;

            v--;

            solver.AddEdge(u,v,dist);

        }

        if(test(ub+)) puts("Infinite");

        else if(!test()) puts("No Solution");

        else

        {

            int L = , R = ub, ans = ;

            while(L <= R)

            {

                int M = L + (R-L)/;

                if(test(M))     //没有负环

                {

                    ans = M;

                    L = M+;

                }

                else R = M-;

            }

            printf("%d\n", ans);

        }

    }

    return ;

}

巴特西

Uva 11478 Halum操作

最新文章

热门文章