本文共 1620 字，大约阅读时间需要 5 分钟。
题意：给a b c要求，b拿的比a拿的多但是不超过c，问你所有人最多差多少
思路：在最短路专题应该能看出来是差分约束，条件是b - a <= c，也就是满足b <= a + c，和spfa的松弛条件相对应，所以我们建一条a到b的边，权值c，然后跑最短路，求出所有差值最大的那个即为答案。应该算是基础的线性差分约束题。
ps：队列超时，这里用栈。
关于差分约束
#include #include #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;const int maxn = 30000+10;const int INF = 0x3f3f3f3f;struct Edge{ int v,cost,next;}edge[1500000];int head[maxn],tot;void init(){ tot = 0; memset(head,-1,sizeof(head));}void addEdge(int u,int v,int cost){ edge[tot].v = v; edge[tot].cost = cost; edge[tot].next = head[u]; head[u] = tot++;}bool vis[maxn];int cnt[maxn];int dist[maxn];bool spfa(int start,int n){ memset(vis,false,sizeof(vis)); for(int i = 1;i <= n;i++) dist[i] = INF; vis[start] = true; dist[start] = 0; stack q; while(!q.empty()) q.pop(); q.push(start); memset(cnt,0,sizeof(cnt)); cnt[start] = 1; while(!q.empty()){ int u = q.top(); q.pop(); vis[u] = false; for(int i = head[u];i != -1;i = edge[i].next){ int v = edge[i].v; if(dist[v] > dist[u] + edge[i].cost){ dist[v] = dist[u] + edge[i].cost; if(!vis[v]){ vis[v] = true; q.push(v); if(++cnt[v] > n) return false; } } } } return true;}int main(){ int n,m; init(); int a,b,c; // b - a <= c : when b > a + c then change scanf("%d%d",&n,&m); while(m--){ scanf("%d%d%d",&a,&b,&c); addEdge(a,b,c); } spfa(1,n); int Max = 0; for(int i = 2;i <= n;i++){ if(dist[i] < INF) Max = max(Max,dist[i]); } printf("%d\n",Max); return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/9485719.html