本文主要是介绍差分约束题目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
P5960 【模板】差分约束算法
#include <bits/stdc++.h>
using namespace std;
int n, m, v, u, w, dis[5001];
bool flag;
struct node{int from, to, weight;
}edge[5001];
int main()
{cin >> n >> m;memset(dis, 0x3f, sizeof(dis));dis[1]=0;for(int i=1; i<=m; ++i){cin >> edge[i].to >> edge[i].from >> edge[i].weight;}for(int i=1; i<n; ++i){for(int j=1; j<=m; ++j){u=edge[j].from;v=edge[j].to;w=edge[j].weight;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;} }}for(int i=1; i<=m; ++i){u=edge[i].from;v=edge[i].to;w=edge[i].weight;if(dis[v]>dis[u]+w){flag=true;break;}}if(flag){cout << "NO";return 0;}for(int i=1; i<=n; ++i){cout << dis[i] << " ";}return 0;
}P1993 小 K 的农场 （判断是否有解）
最短路, 有负环, 则无解
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5010, M=20010;
LL dis[N];
int n, m, cnt[N], head[N], tot, opt, u, v, w, a, b, c;
bool vis[N];
queue<int> q;
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
bool spfa()
{memset(dis, 0x3f, sizeof(dis));dis[0]=0;vis[0]=true;q.push(0);while(!q.empty()){u=q.front();vis[u]=false;q.pop();for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;cnt[v]++;if(cnt[v]>=n){return false;} if(!vis[v]){q.push(v);vis[v]=true;}} }}return true;
}
int main()
{scanf("%d %d", &n, &m);while(m--){scanf("%d", &opt);if(opt==1){ //a-b>=c, 转换为b<=a-c scanf("%d %d %d", &a, &b, &c); add(a, b, -c);}else if(opt==2){ //a-b<=c, 转换为a<=b+c scanf("%d %d %d", &a, &b, &c); add(b, a, c);}else if(opt==3){ //a>=b, 并且b>=a scanf("%d %d", &a, &b); add(a, b, 0);add(b, a, 0);}}for(int i=1; i<=n; ++i){add(0, i, 0);}if(!spfa()){ //有负环 printf("No"); }else{printf("Yes");}return 0;
}最长路, 有正环, 则无解
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5010, M=20010;
LL dis[N];
int n, m, cnt[N], head[N], tot, opt, u, v, w, a, b, c;
bool vis[N];
queue<int> q;
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
bool spfa()
{memset(dis, -0x3f, sizeof(dis));dis[0]=0;vis[0]=true;q.push(0);while(!q.empty()){u=q.front();vis[u]=false;q.pop();for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]<dis[u]+w){dis[v]=dis[u]+w;cnt[v]++;if(cnt[v]>=n){return false;} if(!vis[v]){q.push(v);vis[v]=true;}} }}return true;
}
int main()
{scanf("%d %d", &n, &m);while(m--){scanf("%d", &opt);if(opt==1){ //a-b>=c, 转换为a>=b+c scanf("%d %d %d", &a, &b, &c); add(b, a, c);}else if(opt==2){ //a-b<=c, 转换为b>=a-c scanf("%d %d %d", &a, &b, &c); add(a, b, -c);}else if(opt==3){ //a>=b, 并且b>=a scanf("%d %d", &a, &b); add(b, a, 0);add(a, b, 0);}}for(int i=1; i<=n; ++i){ //di>=0, 转换为di>=d0+0 add(0, i, 0);}if(!spfa()){ //有正环 printf("No"); }else{printf("Yes");}return 0;
}P6145 [USACO20FEB]Timeline G （最长路找最小值）
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=100010, M=300010;
int n, m, c, s, head[N], tot, u, v, w, a, b, x;
LL dis[N];
bool vis[N];
queue<int> q;
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
void spfa() //最长路, 找最小值
{memset(dis, -0x3f, sizeof(dis));//从超级源点出发 dis[0]=0;vis[0]=true;q.push(0);while(!q.empty()){u=q.front();vis[u]=false;q.pop();for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]<dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){q.push(v);vis[v]=true;}}}}
}
int main()
{scanf("%d %d %d", &n, &m, &c);for(int i=1; i<=n; ++i){scanf("%d", &s);//第i次挤奶的日期大于等于s[i], dis[i]>=dis[0]+s[i]add(0, i, s);//第i次挤奶的日期小于等于m, dis[i]<=dis[0]+m, dis[0]>=dis[i]-madd(i, 0, -m);}while(c--){scanf("%d %d %d", &a, &b, &x);//第 b 次挤奶在第 a 次挤奶结束至少 x 天后进行//dis[b]-dis[a]>=x, 即 dis[b]>=dis[a]+xadd(a, b, x); }spfa();for(int i=1; i<=n; ++i){printf("%lld\n", dis[i]); }return 0;
}P1250 种树 （最长路找最小值）
#include <bits/stdc++.h>
using namespace std;
const int N=30010, M=65010;
int n, h, u, v, w, head[N], tot, dis[N];
bool vis[N];
queue<int> q;
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
void spfa()
{memset(dis, -0x3f, sizeof(dis));dis[0]=0;vis[0]=true;q.push(0);while(!q.empty()){u=q.front();vis[u]=false;q.pop();for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]<dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){vis[v]=true;q.push(v);}}}}
}
int main()
{scanf("%d %d", &n, &h);while(h--){scanf("%d %d %d", &u, &v, &w);u++;v++;//dis[v]-dis[u-1]>=w, 转换为最长路形式: dis[v]>=dis[u-1]+wadd(u-1, v, w);}for(int i=0; i<=n; ++i){add(i, i+1, 0); //dis[i+1]-dis[i]>=0, dis[i+1]>=dis[i]+0add(i+1, i, -1); //dis[i+1]-dis[i]<=1, dis[i]>=dis[i+1]-1}spfa();printf("%d", dis[n+1]);return 0;
}#include <bits/stdc++.h>
using namespace std;
const int N=30010, M=65010;
int n, h, u, v, w, head[N], tot, dis[N];
bool vis[N];
queue<int> q;
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
void spfa()
{memset(dis, -0x3f, sizeof(dis));dis[0]=0;vis[0]=true;q.push(0);while(!q.empty()){u=q.front();vis[u]=false;q.pop();for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]<dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){vis[v]=true;q.push(v);}}}}
}
int main()
{scanf("%d %d", &n, &h);while(h--){scanf("%d %d %d", &u, &v, &w);//dis[v]-dis[u-1]>=w, 转换为最长路形式: dis[v]>=dis[u-1]+wadd(u-1, v, w);}for(int i=0; i<n; ++i){add(i, i+1, 0); //dis[i+1]-dis[i]>=0, dis[i+1]>=dis[i]+0add(i+1, i, -1); //dis[i+1]-dis[i]<=1, dis[i]>=dis[i+1]-1}spfa();printf("%d", dis[n]);return 0;
}P1260 工程规划
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1010, M=6010;
int n, m, head[N], tot, cnt[N], u, v, w;
bool vis[N];
queue<int> q;
LL dis[N];
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
//求最长路
bool spfa()
{memset(dis, -0x3f, sizeof(dis));vis[0]=true;dis[0]=0;q.push(0);while(!q.empty()){u=q.front();q.pop();vis[u]=false; //标记点u不在队列中 for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]<dis[u]+w){ //松弛 dis[v]=dis[u]+w;cnt[v]++; //点v被松弛的次数 if(cnt[v]>=n){ //达到了n, 则有正环, 说明无解 return false;}if(!vis[v]){ //如果点v没在队列中, 则入队 q.push(v);vis[v]=true;}}}}return true;
}
int main()
{scanf("%d %d", &n, &m);for(int i=1; i<=m; ++i){scanf("%d %d %d", &u, &v, &w);add(u, v, -w); //u-v<=b， 转换为v>=u-b, 建一条从u到v, 边权为-w的边, 求最长路, 得到最小值 }for(int i=1; i<=n; ++i){ //所有的开始时间必须大于等于零, ti>=0, 相当于 ti>=t0+0, add(0, i, 0); //建一条从0点到i点的边, 边权为0 }if(!spfa()){printf("NO SOLUTION");}else{for(int i=1; i<=n; ++i){printf("%lld\n", dis[i]);}}return 0;
}P3275 [SCOI2011]糖果
#include <bits/stdc++.h>
using namespace std;
const int N=100010, M=300010;
#define LL long long
int n, k, x, a, b, tot, head[N];
LL dis[N], ans, cnt[N];
bool vis[N];
queue<int> q;
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
bool spfa()
{memset(dis, -0x7f, sizeof(dis));q.push(0);dis[0]=0;vis[0]=true;cnt[0]++;int u, v, w;while(!q.empty()){u=q.front();q.pop();vis[u]=false;for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]<dis[u]+w){dis[v]=dis[u]+w;cnt[v]++;if(cnt[v]>=n){return false;}if(!vis[v]){vis[v]=true;q.push(v);}}}}return true;
}
int main()
{scanf("%d %d", &n, &k);for(int i=1; i<=k; ++i){scanf("%d %d %d", &x, &a, &b);if(x==1){add(b, a, 0);add(a, b, 0);}else if(x==2){add(a, b, 1);if(a==b){printf("-1");return 0;}}else if(x==3){add(b, a, 0);}else if(x==4){add(b, a, 1);if(a==b){printf("-1");return 0;}}else if(x==5){add(a, b, 0);}}for(int i=n; i>=1; --i){add(0, i, 1);}if(!spfa()){printf("-1");}else{for(int i=1; i<=n; ++i){ans+=dis[i];}printf("%lld", ans);}return 0;
}P4878 [USACO05DEC]Layout G （好题）
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1010, M=40010;
const LL INF=0x3f3f3f3f3f3f3f3f; //long long 8字节, 需要写8个3x
int n, ml, md, a, b, d, head[N], tot, cnt[N], u, v, w;
bool vis[N];
LL dis[N];
queue<int> q, empty;
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
bool spfa0()
{memset(dis, 0x3f, sizeof(dis));vis[0]=true; dis[0]=0;q.push(0);while(!q.empty()){u=q.front();vis[u]=false;q.pop();for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;cnt[v]++;if(cnt[v]>=n){return false; //有负环, 且n在负环上 }if(!vis[v]){vis[v]=true;q.push(v);} }}}return true; //一定要写返回值, 不然默认返回false
}
LL spfa1()
{memset(dis, 0x3f, sizeof(dis));memset(vis, 0, sizeof(vis));swap(q, empty);vis[1]=true; dis[1]=0;q.push(1);while(!q.empty()){u=q.front();vis[u]=false;q.pop();for(int i=head[u]; i; i=e[i].nex){v=e[i].to;w=e[i].dis;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){vis[v]=true;q.push(v);} }}}if(dis[n]==INF){ //如果从1号点到n好点不可达, 说明不连通, dis[n]>=INF, n号点不受限制 return -2;}else{ //否则返回 return dis[n];}
}
int main()
{scanf("%d %d %d", &n, &ml, &md);while(ml--){scanf("%d %d %d", &a, &b, &d); //求最大值, 跑最短路 //dis[b]-dis[a]<=d, 转换为dis[b]<=dis[a]+d, 建一条从a到b, 边权为d的边 add(a, b, d);}while(md--){scanf("%d %d %d", &a, &b, &d); //求最大值, 跑最短路 //dis[b]-dis[a]>=d, 转换为dis[a]<=dis[b]-d, 建一条从b到a, 边权为-d的边 add(b, a, -d);}//奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。//dis[i+1]-dis[i]>=0, 转换为dis[i]<=dis[i+1]+0, 建一条从i+1到i的边, 边权为0 for(int i=1; i<n; ++i){add(i+1, i, 0);}//添加超级源点, 保证图连通 for(int i=1; i<=n; ++i){add(0, i, 0); } if(!spfa0()){ //从超级源点出发, 判断有负环, 则有矛盾, 无解 printf("-1");}else{ //从1号点出发, 找到n的最短路 printf("%lld", spfa1());}return 0;
} P4878_11.in
5 1 2
2 4 5
2 3 3
3 4 3P4878_11.out
-1P2294 [HNOI2005]狡猾的商人 （稍微带点前缀和）
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=110, M=2200;
int w, n, m, s, t, v, cnt[N], head[N], tot;
LL dis[N];
bool vis[N];
queue<int> q, empty;
struct node
{int to, dis, nex;
}e[M];
void add(int u, int v, int w)
{tot++;e[tot].to=v;e[tot].dis=w;e[tot].nex=head[u];head[u]=tot;
}
bool spfa()
{memset(dis, -0x3f, sizeof(dis)); //最长路, 要初始化为负数 dis[0]=0;vis[0]=true;swap(q, empty);q.push(0);while(!q.empty()){int u=q.front();vis[u]=false;q.pop();for(int i=head[u]; i; i=e[i].nex){int v=e[i].to;int w=e[i].dis;if(dis[v]<dis[u]+w){ //最长路 dis[v]=dis[u]+w;cnt[v]++;if(cnt[v]>=n+2){ //0点1个, 1~n+1个点, 总共n+2个点 return false;}if(!vis[v]){q.push(v);vis[v]=true;}}}}return true;
}
int main()
{scanf("%d", &w);while(w--){scanf("%d %d", &n, &m);tot=0;memset(head, 0, sizeof(head));memset(cnt, 0, sizeof(cnt));memset(vis, 0, sizeof(vis));for(int i=0; i<M; ++i){e[i].nex=0;}while(m--){scanf("%d %d %d", &s, &t, &v);//原来的s是1~n, s-1是0~n-1, 超级源点0被占用, 所以将s和t均加一, 给超级源点0留位置, 不影响结果 s++; t++;//dis[t]-dis[s-1]=v, 可以转换为 dis[t]-dis[s-1]>=v, 并且 dis[t]-dis[s-1]<=v, //转换为最长路的格式: dis[t]>=dis[s-1]+v, 并且dis[s-1]>=dis[t]-v//需要建一条由s-1指向t的边, 边权为v, 并且需要建一条由t指向s-1的边权, 边权为-vadd(s-1, t, v);add(t, s-1, -v); }//建立超级源点0号点到其他点的边, 保证超级源点能到达所有的边 for(int i=1; i<=n+1; ++i){add(0, i, 0);} if(spfa()){printf("true\n");}else{printf("false\n");}}return 0;
}这篇关于差分约束题目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
