首页 > 代码库 > UVA11478 Halum [差分约束系统]
UVA11478 Halum [差分约束系统]
https://vjudge.net/problem/UVA-11478
给定一个有向图，每条边都有一个权值。每次你可以选择一个结点v和一个整数d,把所有以v为终点的边的权值减小d,把所有以v为起点的边的权值增加d,最后让所有边的权值的最小值大于零且尽量大。
该死书上翻译错了 >0不是非负 WA好几次因为这个
考虑每条边的约束，di表示i的halum量
w-dv+du>0
dv-du<w
但求解这个差分约束系统只是让这组不等式成立，最长路和最短路控制的都是单个d的最值而不是最小值最大
那如何最小值最大呢？
二分答案......
那么不等式变为dv-du<w-mid，成立的话说明经过操作后边权可以都比mid大
无解的话就是mid=1,无界的话就是mid=最大边权(不能用1e9，溢出)的时候也成立
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=505,M=3005,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,u,v,w;struct edge{ int v,ne; double w;}e[M];int h[N],cnt=0;inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;}int q[N],head,tail,inq[N],num[N],d[N];inline void lop(int &x){if(x==N) x=1;else if(x==0) x=N-1;}bool spfa(int mid){ head=tail=1; memset(inq,0,sizeof(inq)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) q[tail++]=i,inq[i]=1,d[i]=0; while(head!=tail){ int u=q[head++];inq[u]=0;lop(head); for(int i=h[u];i;i=e[i].ne){ int v=e[i].v,w=e[i].w-mid; if(d[v]>d[u]+w){ d[v]=d[u]+w; if(!inq[v]){ inq[v]=1; if(++num[v]>n) return true; if(d[v]<d[q[head]]) head--,lop(head),q[head]=v; else q[tail++]=v,lop(tail); } } } } return false;}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ cnt=0;memset(h,0,sizeof(h)); int l=1,r=0,ans=0; for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),ins(u,v,w),r=max(r,w); if(spfa(l)){puts("No Solution");continue;} else if(!spfa(r)){puts("Infinite");continue;} else{ while(l<=r){ int mid=(l+r)>>1; if(!spfa(mid)) ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); } }}
UVA11478 Halum [差分约束系统]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。