首页 > 代码库 > uva 11478 Halum(图论-差分约束)
uva 11478 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 | Infinite | |||||
Problem Setter: Md. Mahbubul Hasan |
题目大意:
你可以给每个点的入边加一个值和出边加一个值,问你最小的边权最大是多少?
解题思路:
解题代码:用二分枚举答案假设为x,那么 w(a,b)+sum[a]-sum[b]>=x,这些不等式构成了差分约束系统。
<pre name="code" class="cpp">#include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; const int maxn=510; const int maxm=6000; const int inf=100000; struct edge{ int u,v,w,next; }e[maxm]; int head[maxn],cnt,n,m,maxr; int dis[maxn],num[maxn]; bool visited[maxn]; vector <edge> v; void input(){ maxr=-(1<<30); v.clear(); v.resize(m); for(int i=0;i<m;i++){ scanf("%d%d%d",&v[i].u,&v[i].v,&v[i].w); if(v[i].w>maxr) maxr=v[i].w; } } bool spfa(){ for(int i=0;i<=n;i++){ dis[i]=inf; visited[i]=false; num[i]=0; } queue <int> q; q.push(0); visited[0]=true; dis[0]=0; num[0]++; while(!q.empty()){ int s=q.front(); q.pop(); visited[s]=false; for(int i=head[s];i!=-1;i=e[i].next){ int d=e[i].v; if(dis[d]>dis[s]+e[i].w){ dis[d]=dis[s]+e[i].w; if(!visited[d]){ visited[d]=true; q.push(d); if(++num[d]>n+1) return false; } } } } return true; } void adde(int u,int v,int w){ e[cnt].u=u,e[cnt].v=v,e[cnt].w=w,e[cnt].next=head[u],head[u]=cnt++; } bool can(int x){ cnt=0; for(int i=0;i<=n;i++) head[i]=-1; for(int i=1;i<=n;i++) adde(0,i,0); for(int i=0;i<m;i++){ adde(v[i].u,v[i].v,v[i].w-x); } return spfa(); } void solve(){ if(can(maxr+1)) { printf("Infinite\n"); return; } if(!can(1)) { printf("No Solution\n"); return; } int l=1,r=maxr+1; while(l<r){ int mid=(l+r)/2; if(!can(mid)) r=mid; else l=mid+1; } printf("%d\n",r-1); } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ input(); solve(); } return 0; }