UVa11478 - Halum(差分約束)

UVa11478 - Halum(差分約束)

Problem H Halum Time Limit : 3 seconds

You are given a directed graph G(V,E) with a set of vertices and edges. Each edge (i,j) that connects some vertex i to vertex j has an integer cost associated with that edge.

Define the operation Halum(v, d) to operate on a vertex v using an integer d as follows: subtract d from the cost of all edges that enter v and add d to the cost of every edge that leaves v.

As an example of that operation, consider graph G that has three vertices named (1, 2, 3) and two edges. Edge (1, 2) has cost -1, and edge (2,3) has cost 1. The operation Halum(2,-3) operates on edges entering and leaving vertex 2. Thus, edge (1, 2) gets cost -1-(-3)=2 and the edge (2, 3) gets cost 1 + (-3) = -2.

Your goal is to apply the Halum function to a graph, potentially repeatedly, until every edge in the graph has at least a certain cost that is greater than zero. You have to maximize this cost.

Input

Two space-separated integers per case: V(V≤500) and E(E≤2700). E lines follow. Each line represents a directed edge using three space-separated integers (u, v, d). Absolute value of cost can be at most 10000.

Output

If the problem is solvable, then print the maximum possible value. If there is no such solution print “No Solution”. If the value can be arbitrary large print “Infinite”

Sample Input Sample Output

2 1
1 2 10
2 1
1 2 -10
3 3
1 2 4
2 3 2
3 1 5
4 5
2 3 4
4 2 5
3 4 2
3 1 0
1 2 -1

白書上的例題：白書上說答案為非負，然後彈了n遍，一看題意是大於0。坑爹

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 500+10;
const int maxm = 5700+10;
const int inf = 1e9;
struct edge{
    int v,w,nxt;
}e[maxm];
int nume,ne,nv;
int head[maxn];
queue que;
bool inQue[maxn];
int cnt[maxn];
int dist[maxn];

void init(){
    memset(head,0,sizeof head);
    nume = 1;
}

void addedge(int u,int v,int w){
    e[++nume].nxt = head[u];
    e[nume].v = v;
    e[nume].w = w;
    head[u] = nume;
}

bool SPFA(int dis){
    memset(inQue,0,sizeof inQue);
    memset(cnt,0,sizeof cnt);
    while(!que.empty()) que.pop();
    int src = 0;
    inQue[src] = true;
    que.push(src);
    for(int i = 1; i <= nv; i++) dist[i] = inf;
    dist[src] = 0;
    while(!que.empty()){
        int u = que.front();
        que.pop();
        inQue[u] = false;
        for(int i = head[u]; i ; i = e[i].nxt){
            int v = e[i].v,w = e[i].w - dis;
            if(dist[u]+w < dist[v]){
                dist[v] = dist[u]+w;
                if(!inQue[v]){
                    if(++cnt[v] >= nv+1)
                        return false;
                    inQue[v] = true;
                    que.push(v);
                }
            }
        }
    }
    return true;
}

int binary_ser(){
    int L = 2,R = 10001;
    int ans = 0;
    while(L <= R){
        int mid = (L+R)>>1;
        if(SPFA(mid)){
            L = mid+1;
        }else{
            R = mid-1;
        }
    }
    return R;
}
int main(){

    while(~scanf("%d%d",&nv,&ne)){
        int a,b,c;
        init();
        for(int i = 0; i < ne; i++){
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
        }
        for(int i = 1; i <= nv; i++){
            addedge(0,i,0);
        }
        if(SPFA(10001)){
            printf("Infinite\n");
        }
        else if(!SPFA(1)){
            printf("No Solution\n");
        }else{
            printf("%d\n",binary_ser());
        }
    }

    return 0;
}

Infinite
Infinite
3
1