首页 > 其他 > 详细

UVA 11478 Halum

时间:2015-08-05 00:34:13      阅读:274      评论:0      收藏:0      [点我收藏+]

Halum

Time Limit: 3000ms
Memory Limit: 131072KB
This problem will be judged on UVA. Original ID: 11478
64-bit integer IO format: %lld      Java class name: Main

 

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

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

 

Sample Output

Infinite
Infinite
3
1

 

解题:差分约束

 

技术分享
 1 #include <cstdio>
 2 #include <deque>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 const int maxn = 510;
 7 struct arc {
 8     int to,w,next;
 9     arc(int x = 0,int y = 0,int z = -1) {
10         to = x;
11         w = y;
12         next = z;
13     }
14 } e[500000];
15 int head[maxn],tot,n,m;
16 void add(int u,int v,int w) {
17     e[tot] = arc(v,w,head[u]);
18     head[u] = tot++;
19 }
20 int d[maxn],cnt[maxn];
21 bool in[maxn];
22 bool spfa(int x) {
23     deque<int>q;
24     for(int i = 1; i <= n; ++i) {
25         cnt[i] = 1;
26         d[i] = 0;
27         in[i] = true;
28         q.push_back(i);
29     }
30     while(!q.empty()) {
31         int  u = q.front();
32         q.pop_front();
33         in[u] = false;
34         for(int i = head[u]; ~i; i = e[i].next) {
35             int tmp = e[i].w - x;
36             if(d[e[i].to] > d[u] + tmp) {
37                 d[e[i].to] = d[u] + tmp;
38                 if(!in[e[i].to]) {
39                     if(++cnt[e[i].to] > n) return false;
40                     in[e[i].to] = true;
41                     if(!q.empty() && d[q.front()] > d[e[i].to])
42                         q.push_front(e[i].to);
43                     else q.push_back(e[i].to);
44                 }
45             }
46         }
47     }
48     return true;
49 }
50 int main() {
51     int u,v,w;
52     while(~scanf("%d%d",&n,&m)) {
53         memset(head,-1,sizeof head);
54         int low = 1,high = 0;
55         for(int i = tot = 0; i < m; ++i) {
56             scanf("%d%d%d",&u,&v,&w);
57             add(u,v,w);
58             high = max(high,w);
59         }
60         if(!spfa(1)) puts("No Solution");
61         else if(spfa(high+1)) puts("Infinite");
62         else {
63             int ret;
64             while(low <= high) {
65                 int mid = (low + high)>>1;
66                 if(spfa(mid)) {
67                     ret = mid;
68                     low = mid+1;
69                 } else high = mid - 1;
70             }
71             printf("%d\n",ret);
72         }
73     }
74     return 0;
75 }
View Code

 

UVA 11478 Halum

原文:http://www.cnblogs.com/crackpotisback/p/4703338.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!