差分约束

差分约束系统是形如：

\[\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}
\]

的不等式组。

我们要解决的问题是：求一组解，使得所有的约束条件得到满足；否则判断出无解。

步骤

差分约束系统中的每个约束条件 \(x_i-x_j\leq c_k\) 都可以变形成 \(x_i\leq x_j+c_k\)，这与单源最短路中的三角形不等式 \(dist[y]\leq dist[x]+z\) 非常相似。

因此，可以把每个变量 \(x_i\) 看做图中的一个结点；对于每个约束条件 \(x_i-x_j\leq c_k\)，看作从结点 \(j\) 向结点 \(i\) 连一条长度为 \(c_k\) 的有向边。

ps：如果 \(\{a_1,a_2,\dots,a_n\}\) 是该差分约束系统的一组解，那么对于任意的常数 \(d，\{a_1+d,a_2+d,\dots,a_n+d\}\) 显然也是该差分约束系统的一组解，因为这样做差后 \(d\) 刚好被消掉。

AC·code

#include<bits/stdc++.h>
#define ri register
#define cs const
#define il inline 
using namespace std;
il int rd(){
    ri int x=0,f=1;ri char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return x*f;
}
il void wt(int x){
    if(x<0) x=-x,putchar('-');
    if(x>=10) wt(x/10);
    return putchar(x%10+48),void();
}
cs int N=5e3+5,inf=0x7fffffff;
int dis[N],vis[N],cnt[N],nw;
int n,m,s;
struct edge{
    int v,w;
}ovo;
vector<edge> e[N];
queue<int> sp;
il bool spfa(int st,int n){
//    memset(dis,0x3f,sizeof(dis));
    for(ri int i=1;i<=n;++i) dis[i]=inf;
    dis[st]=0;
    sp.push(st);
    vis[st]=1;
    while(!sp.empty()){
        nw=sp.front();
        sp.pop(),vis[nw]=0;
        for(ri unsigned int i=0;i<e[nw].size();++i){
            if(dis[nw]+e[nw][i].w<dis[e[nw][i].v]){
                dis[e[nw][i].v]=dis[nw]+e[nw][i].w;
                cnt[e[nw][i].v]=cnt[nw]+1;
                if(cnt[e[nw][i].v]>=n) return 0;
                if(!vis[e[nw][i].v]){
                    vis[e[nw][i].v]=1;
                    sp.push(e[nw][i].v);
                } 
            }
        }
    }
    return 1;
}
signed main(){
    n=rd(),m=rd();
    for(ri int i=1,c,c1,y;i<=m;++i){
        c=rd(),c1=rd(),y=rd();
        e[c1].push_back({c,y});
    }
    for(ri int i=1;i<=n;++i){
        e[0].push_back({i,0});
    }
    if(!spfa(0,n+1)) putchar('N'),putchar('O');
    else{
        for(ri int i=1;i<=n;++i){
            wt(dis[i]),putchar('\n'); 
        }
    }
    return 0;
}

原文链接: https://www.cnblogs.com/windymoon/p/17078563.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/315097

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

差分约束

差分约束

步骤

相关推荐