[差分约束] P3275 [SCOI2011] 糖果 & P1993 小K的农场 (洛谷) & poj 3169 Layout
差分约束系统有两种方式可以求解，最短路和最长路。当我们把不等式整理成d[a]+w<=d[b]时，我们求最长路。整理成d[a]+w>=d[b]时，我们求最短路。
最长路 找最小值 <= 数据最低的极限
最短路 找最大值 >= 数据最大的极限
这个是极限是存在得 不能<=-inf 大于 +inf 什么得
注意全部建图方向 都根据题 选取一个符号来决定
ps 对于某些不连通的图 建个0点 联通什么的
https://www.luogu.org/problemnew/show/P1993
P1993 小K的农场
差分约束 跑最短路 看负环就好 <= 不能最大得极限不是 —INF
要有
1：表示农场 a 比农场 b 至少多种植了 c 个单位的作物。即a>=b+c
2：表示农场 a 比农场 b 至多多种植了 c 个单位的作物。即a<=b+c
3：表示农场 a 与农场 b 种植数一样 即a=b 可以表示为 a - b == 0 和 b - a = = 0
以下 有找最短路 最长路 dis数组三角不等式 决定 c(u,v) 便是方向和权值
对于 1 来说
disa>=disb + c(a,b) 所以建边 a->b c的路
大于小于分清 按不等式走
这题也可以跑最长路 这个时候对于 1来说
disb<= disb-c(b,a) 所以建立 b->a -c 的路
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn = 1e4+5;
bool vis[maxn];
int dis[maxn];
int to[maxn<<2],val[maxn<<2],head[maxn],nxt[maxn<<2];
int cnt;
void add_edge(int a,int b,int v){
to[++cnt]=b;
nxt[cnt]=head[a];
head[a]=cnt;
val[cnt]=v;
}
bool spfa(int u){
vis[u]=1;
for(int i=head[u];i;i=nxt[i])
if(dis[to[i]]>dis[u]+val[i]){
dis[to[i]]=dis[u]+val[i];
if(vis[to[i]])return 0;
if(!spfa(to[i]))return 0;
}
vis[u]=0;
return 1;
}
int main(){
int n,m;
int v,cmd;
int a,b;
cin>>n>>m;
for(int i=1;i<=n;i++) dis[i]=INF;
for(int i=0;i<m;i++){
cin>>cmd;
switch(cmd){
case 1:
cin>>a>>b>>v;
add_edge(b,a,v);
break;
case 2:
cin>>a>>b>>v;
add_edge(a,b,-v);
break;
case 3:
cin>>a>>b;
add_edge(a,b,0);
add_edge(b,a,0);
break;
}
}
for(int i=1;i<=n;i++) add_edge(0,i,0);
dis[0]=0;
if(spfa(0)) cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
P3275 [SCOI2011]糖果
https://www.luogu.org/problemnew/show/P3275
既然是早最少要多少 就跑最长路 看最小值 答案是每个人到0的距离和
差分约束 跑最长路 看正环就好 >= 不能最底得极限不存在 是+INF
后面那个题 记得开LL 然后 倒这建0到（1，n） 的线 卡SPFAorz
这图建立就容易了 有了上一题
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5+5;
bool vis[maxn];
ll dis[maxn];
int to[maxn<<2],val[maxn<<2],head[maxn],nxt[maxn<<2];
int cnt;
void ade(int a,int b,int v){
to[++cnt]=b;
nxt[cnt]=head[a];
head[a]=cnt;
val[cnt]=v;
}
bool spfa(int u){
vis[u]=1;
for(int i=head[u];i;i=nxt[i])
if(dis[to[i]]<dis[u]+val[i]){
dis[to[i]]=dis[u]+val[i];
if(vis[to[i]])return 0;
if(!spfa(to[i]))return 0;
}
vis[u]=0;
return 1;
}
int main(){
int n,m;
int v,cmd;
int a,b;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>cmd>>a>>b;
if(cmd==1) ade(a,b,0),ade(b,a,0);
if(cmd==2) ade(a,b,1);
if(cmd==3) ade(b,a,0);
if(cmd==4) ade(b,a,1);
if(cmd==5) ade(a,b,0);
}
for(int i=n;i>=1;i--) ade(0,i,1),dis[i]=-INF;
dis[0]=0;
if(!spfa(0)){
cout<<-1<<endl;
}else{
ll ans=0;
for(int i=1;i<=n;i++) ans+=dis[i];
cout<<ans<<endl;
}
return 0;
}
Layout
http://poj.org/problem?id=3169
数据保证 大的在小的 左边
找 1和n最远距离 跑最短路 数据最大值是上线
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn = 1e4+5;
bool vis[maxn];
int dis[maxn];
int to[maxn<<2],val[maxn<<2],head[maxn],nxt[maxn<<2];
int cnt;
void add_edge(int a,int b,int v){
to[++cnt]=b;
nxt[cnt]=head[a];
head[a]=cnt;
val[cnt]=v;
}
bool spfa(int u){
vis[u]=1;
for(int i=head[u];i;i=nxt[i])
if(dis[to[i]]>dis[u]+val[i]){
dis[to[i]]=dis[u]+val[i];
if(vis[to[i]])return 0;
if(!spfa(to[i]))return 0;
}
vis[u]=0;
return 1;
}
int main(){
int n,m1,m2;
int v,cmd;
int a,b;
cin>>n>>m1>>m2;
for(int i=1;i<=n;i++) dis[i]=INF;
for(int i=0;i<m1;i++){
cin>>a>>b>>v;
add_edge(a,b,v);
}
for(int i=0;i<m2;i++){
cin>>a>>b>>v;
add_edge(b,a,-v);
}
// for(int i=1;i<=n;i++) add_edge(0,i,0);
dis[1]=0;
if(!spfa(1)) cout<<-1<<endl;
else if(dis[n]==INF) cout<<-2<<endl;
else cout<<dis[n]<<endl;
//else cout<<"No\n";
return 0;
}
查看12道真题和解析
