首页 > 代码库 > UVa11478 - Halum(差分约束)
UVa11478 - Halum(差分约束)
Problem H | Halum | Time Limit : 3 seconds | ||
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 白书上的例题:白书上说答案为非负,然后弹了n遍,一看题意是大于0。坑爹 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> #include <queue> 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<int> 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 = http://www.mamicode.com/0;> | Infinite |