下面的內容可能會好好寫一下，畢竟自己也踩了好幾次坑，
建議先看一下題面什么意思，我不會LATEX，就不碼了，
P5960差分約束
一些簡單的變形
對于各個約束條件，
主要就是形如 \(x_i-y_i<=c_i\) 的式子
稍加變形，即有\(x_i<=y_i+c_i\)
不難看出，這個式子與最短路中的松弛操作很像，那么，我可以考慮將這個問題轉換成一個最短路問題，
那么，重點來了
如何建圖？
參照該式子與最短路的高度相似性，我們可以自然地想出令\(x_i\)表示源點到點\(i\)的距離，
于是，我們便有了設定一個超級源點s，到每個點建一條邊權為0的邊，
\(x_i\)與\(y_i\)之間的邊如何建呢？
我們為了讓\(x_i<=y_i+c_i\)成立，那么，我們就可以從\(y_i\)到\(x_i\)建立一條權值為\(c_i\)的邊，來使得跑完最短路之后，恒有\(x_i\not>y_i+c_i\)，
如何判斷無解？
此時，又有了第二個問題，可能該式子永遠不可能滿足，怎么判斷？
我們之前已經把這個問題約歸到了最短路上，那么，解不存在，等價于最短路不存在，等價于圖中存在負環，
所以，我們就可以用SPFA來跑最短路，同時判斷負環
綜上，便可以求解該類的差分約束問題的一組解，
如果形式不一樣怎么辦？
通過數學手段變形，比如同乘\(-1\)，將 \(=\) 拆成 \(>=\) and \(<=\)等,這里就不贅述了，
Code
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const int N=5e6+5;
int n,m;
struct edges
{
int u,v,w,next;
}edge[N];
int edgecnt;
int head[N];
void addedge(int u,int v,int w)
{
edge[++edgecnt].next=head[u];
edge[edgecnt].u=u;edge[edgecnt].v=v;edge[edgecnt].w=w;
head[u]=edgecnt;
}
int dist[N];
bool inQueue[N];
int viscnt[N];
queue<int> q;
bool SPFA(int s)
{
memset(dist,63,sizeof(dist));
dist[s]=0;q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
inQueue[u]=false;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].v;int w=edge[i].w;
if(dist[v]>dist[u]+w)
{
dist[v]=dist[u]+w;
if(!inQueue[v])
{
inQueue[v]=true;
viscnt[v]++;
if(viscnt[v]==n+1) return false;
q.push(v);
}
}
}
}
return true;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,c;cin>>a>>b>>c;
addedge(b,a,c);
}
for(int i=1;i<=n;i++)
{
addedge(0,i,0);
}
if(!SPFA(0))
{
cout<<"NO";
return 0;
}
else
{
for(int i=1;i<=n;i++)
cout<<dist[i]<<' ';
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/178324.html
標籤：其他
上一篇：力扣初級演算法（一）【陣列】
下一篇：如何把應用程式遷移到k8s