差分约束总结
问题模型
求解由若干不等式限制的一组最大或最小未知数解
思想
首先我们来看看最短路的松弛操作，以(spfa)为例：
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!inq[v]) inq[v]=0,q.push(v);
}
即当图中存在(dis[v]>dis[u]+w)时，就立刻松弛使其满足(dis[v]le dis[u]+w)，所以我们可以容易得到，当一张图跑完一次最短路后，对于任意一组(u,v)均满足(dis[v]le dis[u]+w)，由此我们可以联想到可以将不等式转化为图中两点，对图跑最短路，不断松弛，让图中所有节点满足不等式(dis[v]le dis[u]+w)，便就是在让所有未知数满足所有不等式，求解一次差分约束系统的解。
最短路、最长路其实均使图中所有节点满足所有不等式，但是对于差分约束系统，跑最短路能得到最大的未知数，最长路能跑到最小的未知数。这是因为，不管是最短路、最长路都是尽可能地使不等式趋向取等。比如，最短路是使不等式(dis[v]le dis[u]+w)尽可能取等，在此我们可以将(dis[u]+w)视为一个常数(K)，当不等式(dis[v]le K)取等时，自然(dis[v])取到最大值，所以最短路求得未知数最大，最长路求得未知数最小
例题
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXM 300005
using namespace std;
int n,k;
int head[MAXM],nxt[MAXM],vv[MAXM],ww[MAXM],tot;
long long ans;
inline void add_edge(int u, int v, int w){
vv[++tot]=v;
ww[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
int dis[MAXM];
int cnt[MAXM];
bool inq[MAXM];
queue <int> q;
inline int read()
{
int s=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
inline bool spfa(int s){
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
inq[u]=0;
for(register int i=head[u];i;i=nxt[i]){
int v=vv[i];
if(dis[v]<dis[u]+ww[i]){
dis[v]=dis[u]+ww[i];
cnt[v]=cnt[u]+1;
if(cnt[v]>=n+1) return 0;
if(!inq[v]) inq[v]=1,q.push(v);
}
}
}
return 1;
}
int main()
{
n=read(),k=read();
bool isOK=1;
for(int i=1;i<=k;++i){
int x,a,b;x=read(),a=read(),b=read();
if(x==1) add_edge(a,b,0),add_edge(b,a,0);
else if(x==2){
if(a==b){
isOK=0;
break;
}
add_edge(a,b,1);
}else if(x==3){
add_edge(b,a,0);
}
else if(x==4){
if(a==b){
isOK=0;
break;
}
add_edge(b,a,1);
}else if(x==5){
add_edge(a,b,0);
}
}
if(!isOK){
puts("-1");
return 0;
}
for(register int i=n;i>=1;--i)
add_edge(0,i,1);
if(spfa(0)){
for(register int i=1;i<=n;++i)
ans+=dis[i];
printf("%lld", ans);
}else puts("-1");
return 0;
}
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXM 300005
using namespace std;
int n,k;
int head[MAXM],nxt[MAXM],vv[MAXM],ww[MAXM],tot;
inline void add_edge(int u, int v, int w){
vv[++tot]=v;
ww[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
inline int read()
{
int s=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
int dis[MAXM];
bool vis[MAXM];
queue <int> q;
bool spfa(int u){
vis[u]=1;
for(register int i=head[u];i;i=nxt[i]){
int v=vv[i];
if(dis[v]<dis[u]+ww[i]){
dis[v]=dis[u]+ww[i];
if(vis[v]) return 0;
if(!spfa(v)) return 0;
}
}
vis[u]=0;
return 1;
}
int main()
{
n=read(),k=read();
bool isOK=1;
for(int i=1;i<=k;++i){
int x,a,b,c;x=read(),a=read(),b=read();
if(x==1){
if(a==b){
isOK=0;
break;
}
c=read(),add_edge(b,a,c);
}else if(x==2){
if(a==b){
isOK=0;
break;
}
c=read(),add_edge(a,b,-1*c);
}else
add_edge(a,b,0),add_edge(b,a,0);
}
if(!isOK){
puts("No");
return 0;
}
for(register int i=n;i>=1;--i)
add_edge(0,i,0);
memset(dis, -0x3f, sizeof(dis)); dis[0] = 0;
if(spfa(0))
puts("Yes");
else puts("No");
return 0;
}
#include <cstdio>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
#define MAXM 30003
using namespace std;
int n,ml,md;
int head[MAXM],nxt[MAXM],vv[MAXM],ww[MAXM],tot;
inline void add_edge(int u, int v, int w){
ww[++tot]=w;
vv[tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
int dis[MAXM],cnt[MAXM];
bool inq[MAXM];
queue <int> q;
inline bool spfa(int s){
memset(dis, 0x3f, sizeof(dis));
dis[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();inq[s]=0;
for(register int i=head[u];i;i=nxt[i]){
int v=vv[i],w=ww[i];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>n) return 0;
if(!inq[v]) inq[v]=1,q.push(v);
}
}
}
return 1;
}
int main()
{
scanf("%d %d %d", &n, &ml, &md);
while(ml--){
int a,b,d;scanf("%d %d %d", &a, &b, &d);
add_edge(a,b,d);
}
while(md--){
int a,b,d;scanf("%d %d %d", &a, &b, &d);
add_edge(b,a,-1*d);
}
for(register int i=1;i<=n;++i)
add_edge(0,i,0);
if((!spfa(0))||(!spfa(1))) printf("-1");
else if(dis[n]==INF) printf("-2");
else printf("%d
", dis[n]-dis[1]);
/*for(register int i=0;i<=n;++i)
printf("%d
", dis[i]);*/
return 0;
}