【模板】差分約束算法

題意：

題解：

模板題
算法講解
給出一組包含 m 個(gè)不等式，有 n 個(gè)未知數(shù)。求任意一組滿足這個(gè)不等式組的解，或判定無解。

連邊之后跑最短路，保證每個(gè)連通塊都沒有負(fù)環(huán)即可。
也可以建源點(diǎn)s = 0，s向所有點(diǎn)連0邊，相當(dāng)于1次spfa可以遍歷所有連通塊（注意此時(shí)判負(fù)環(huán)條件 cnt[v]>=N+1）。

代碼：

錯(cuò)誤代碼（有待修改）

#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof a) typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=5e3+9; struct node{int u,v,w,next; }edge[maxn]; int head[maxn]; int tot=0; void add(int u,int v,int w) {edge[++tot].v=v;edge[tot].next=head[u];edge[tot].w=w;head[u]=tot; } int dis[maxn],vis[maxn]; int cnt[maxn]; int n,m; bool spfa(int now) {mem(cnt,0);mem(vis,0);queue<int>q;dis[now]=0;q.push(now);vis[now]=1;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;int w=edge[i].w;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;cnt[v]=cnt[u]+1;if(cnt[v]>=n)return 1;if(vis[v]==0){vis[v]=1;q.push(v);}}}}return 0; } int main() {cin>>n>>m;for(int i=1;i<=n;i++)dis[i]=0x3f;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}for(int i=1;i<=n;i++)if(dis[i]==0x3f){if(spfa(i)){cout<<"NO"<<endl;return 0; }for(int i=1;i<=n;i++){cout<<dis[i]<<" ";}return 0;}return 0; }

正確代碼：

#include<bits/stdc++.h> #define MAXN 5005 #define inf int(16843009) using namespace std; int N,M,s,t; struct edge{int v,w;edge(int v=0, int w=0):v(v),w(w){}; }; vector<edge> adj[MAXN]; int d[MAXN], cnt[MAXN]; bool inq[MAXN];bool spfa(int s){memset(d, 1, sizeof(d));queue<int> q;d[s] = 0; q.push(s); inq[s] = 1;int u,v,w;while(!q.empty()){ u = q.front(); q.pop(); inq[u] = 0;for(int i=0;i<adj[u].size();i++){v = adj[u][i].v; w = adj[u][i].w;if(d[u] + w < d[v]){d[v] = d[u] + w;cnt[v] = cnt[u] + 1;//cnt[v] = s->v最短路包含的邊數(shù) if(cnt[v] >= N+1) return 1;//判負(fù)環(huán) if(inq[v]==0){q.push(v); inq[v] = 1;} }}} return 0; }int main(){scanf("%d%d", &N, &M);int u,v,w;for(int i=1;i<=M;i++){scanf("%d%d%d", &v, &u, &w);adj[u].push_back(edge(v,w));}s = 0;for(int i=1;i<=N;i++){adj[0].push_back(edge(i,0));}if(spfa(0)){printf("NO\n");return 0;}for(int i=1;i<=N;i++){printf("%d ", d[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【模板】差分约束算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。