差分約束 C++ 算法例題

差分約束

差分約束 是一種特殊的 n 元一次不等式組，m 個約束條件，可以組成形如下的格式：
$\begin{cases} x_1-x_1^{'} \le y_1 \\ x_2-x_2^{'} \le y_2 \\ \cdots \\ x_m-x_m^{'} \le y_m \end{cases}$
我們的任務是需要求出一組解， $x_1=a_1,x_2=a_2,\cdots,x_n=a_n$

使得不等式組成立，否則為無解

注意到，每個式子都可以變形為 $x_i\le x_i^{'}+y_i$

那么就不難想到，圖論中的 三角不等式 ，即為松弛操作

回憶——

if(dis[edge[i].to]>dis[t]+edge[i].w)dis[edge[i].to]=dis[t]+edge[i].w;

雖說它這里是 >，不過也沒有關系，不用考慮

既然知道了，那我們就按照圖論的方法來解：

設dis[0]=0 ,并且向著每一個節點連接一條權值為0的邊，運用單源最短路，判斷 負權環 ，若有負權環則為無解，否則依次輸出 dis[i]

提到負權環，就不得不提判斷負權環的大佬算法——SPFA！！！

對于那些不廢 SPFA 的同學們，可以翻到我之前的博客區康康~~

好啦，看模板題——

luoguP5960 [模板]差分約束

AC Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,cntedge;
const int MAXM=5e3+5,inf=65;
struct EDGE{int to,w,pre;
}edge[MAXM<<1];
int head[MAXM];
void add(int from,int to,int w)
{edge[++cntedge].to=to;edge[cntedge].w=w;edge[cntedge].pre=head[from];head[from]=cntedge;return;
}
bool vis[MAXM];
int u,v,w,t;
int dis[MAXM],cnt[MAXM];
queue<int> q;
bool spfa()
{q.push(0);cnt[0]++;vis[0]=true;while(!q.empty()){t=q.front();q.pop();vis[t]=false;for(int i=head[t];i;i=edge[i].pre){if(dis[edge[i].to]>dis[t]+edge[i].w){dis[edge[i].to]=dis[t]+edge[i].w;if(vis[edge[i].to]) continue;q.push(edge[i].to);vis[edge[i].to]=true;if(++cnt[edge[i].to]>=n+1)return false;}}}return true;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) add(0,i,0);for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);add(v,u,w);}memset(dis,inf,sizeof(dis));dis[0]=0;if(!spfa())printf("NO\n");else{for(int i=1;i<=n;i++)printf("%d ",dis[i]);printf("\n");}	return 0;
}