UVA 11374 Halum （差分约束系统，最短路）

题意：给定一个带权有向图，每次你可以选择一个结点v 和整数d ，把所有以v为终点的边权值减少d，把所有以v为起点的边权值增加d，最后要让所有的边权值为正，且尽量大。若无解，输出结果。若可无限大，输出结果。否则，输出最小边权的最大值。

思路：差分约束系统用最短路来解。列式子后建图，新图的边就是原图的边，权值也不变。有3种情况，要分开判断。

　　（1）若连最小的权值1都达不到，肯定无解。

　　（2）若可以超过所给边的最大权值，那么最小权值肯定可以继续增大。

　　（3）接下来用二分猜答案，答案范围在[1,big]。只要无负环，就是可取的。

　　注意：很容易超时，优化一下spfa吧。

700ms+

#include <bits/stdc++.h>

#define INF 0x7f7f7f7f

#define pii pair<int,int>

#define LL unsigned long long

using namespace std;

const int N=;

struct node

{

    int from,to,cost;

    node(){};

    node(int from,int to,LL cost):from(from),to(to),cost(cost){};

}edge[];

vector<int > vect[N];

int edge_cnt;

void add_node(int from,int to,int cost)

{

    edge[edge_cnt]=node(from,to,cost);

    vect[from].push_back(edge_cnt++);

}

int inq[N], cost[N], cnt[N];

bool spfa(int s, int n, int d)

{

    memset(cost, , sizeof(cost));

    memset(inq, , sizeof(inq));

    memset(cnt, , sizeof(cnt));

    deque<int> que(,s);

    inq[s]=;

    while(!que.empty())

    {

        int x=que.front();que.pop_front();

        inq[x]=;

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

        {

            node e=edge[vect[x][i]];

            if(cost[e.to]>cost[x]+e.cost-d )

            {

                cost[e.to]=cost[x]+e.cost-d;

                if(!inq[e.to])

                {

                    inq[e.to]=;

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

                    //优化很有用

                    if(!que.empty()&&cost[e.to]<cost[que.front()])    que.push_front(e.to);

                    else    que.push_back(e.to);

                }

            }

        }

    }

    return true;

}

int cal(int s,int n, int L, int R)

{

    while(L<R)

    {

        LL mid=L+(R-L+)/;

        if( spfa(s, n, mid)  )    L=mid;    //不产生环，则满足要求

        else    R=mid-;        //大过头了也可能产生环的

    }

    return L;

}

int main()

{

    freopen("input.txt", "r", stdin);

    int n, m, a, b, c;

    while(~scanf("%d %d",&n,&m))

    {

        edge_cnt=;

        memset(edge,,sizeof(edge));

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

        int big=;

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

        {

            scanf("%d %d %d", &a, &b, &c);

            add_node(a, b, c);

            big=max(big, c);

        }

        for(int i=; i<=n; i++) add_node(, i, );  //加源点

        if( spfa(, n, big+) )   //如果连最大权都能超过，肯定可以inf。因为若有环，一般都是有权加就有权减。

        {

            puts("Infinite");

            continue;

        }

        if( !spfa(, n, ) )    //没有大于0的边

        {

            puts("No Solution");

            continue;

        }

        printf("%d\n",  cal(, n, , big) );

    }

    return ;

}

AC代码