题目戳这里：https://vjudge.net/problem/UVA-11478 题目大意：给定一个权值，边有权值，每次可以选择一个点v和一个整数d，把所有以v为终点的边的权值减少d，以v为起点的边的权值加d，最后让所有边权的最小值非负且最大，如果这个值大于10000输出Infinite,如果非正输出No Solution。 对于每个点有我们把它的总操作权值设为sum,那么对于一条边（a，b）那么它应该满足w（a，b）+sum[a]-sum[b] >= v 这个v是我们二分的答案，然后整理一下就是sum[b]-sum[a] <= w(a,b)-v 我们根据这个建立差分约束系统，然后跑一边spfa判断有没有负环。 代码如下：
#include<cstdio> #include<cstring> #include<queue> #include<iostream> #include<algorithm> #define del(a,b) memset(a,b,sizeof(a)) #define N 50010 #define inf 0x3f3f3f3f using namespace std; int n,num,head[N],m; struct Edge{ int v,next,w; }; Edge e[10*N]; void adde(int i,int j,int w){ e[++num].v=j; e[num].next=head[i]; e[num].w=w; head[i]=num; } int vis[N],dis[N],s,in[N]; bool spfa(){ del(dis,63); del(vis,0); queue<int>q; while(!q.empty())q.pop(); q.push(s); vis[s]=1; dis[s]=0; while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; if(!vis[v]){ vis[v]=1; q.push(v); in[v]++; if(in[v]>n)return false; } } } } return true; } int a[N],b[N],c[N]; bool check(int mid){ s=N-1; del(e,0); del(head,0); del(in,0); num=0; for(int i=1;i<=m;i++) adde(a[i],b[i],c[i]-mid); for(int i=1;i<=n;i++) adde(s,i,0); if(spfa()){ return true; } else return false; } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); int l=1,r=10005,ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(mid))ans=mid,l=mid+1; else r=mid-1; } if(ans==10005) printf("Infinite\n"); else if(ans!=0) printf("%d\n",ans); else printf("No Solution\n"); } }