C++基础:差分约束系统

C++基础:差分约束系统,第1张

C++基础:差分约束系统

基本思路:利用最短路中di≤dj+c(j指向i,边权为c,此指算法结束后)将求解三角不等式组转换为(单源)最短路问题

三角不等式(组): xi≤xj+ck   其中xi、xj是自变量,ck是常量

差分约束系统有如下功能:

  • 求不等式组的可行解

    源点需要满足条件:从原点出发,一定可以走到所有的边。故可设“超级源点

    超级源点:与每一个点相连的虚拟源点

    步骤:

    1. 先将每个不等式xi≤xj+ck转化成一条从xj走向xi,长度为ck的一条边
    2. 找一个超级源点,使得该院点一定可以遍历到所有边
    3. 从源点求一边单源最短路

    结果:

    1. 如果存在负环,则该不等式组无解
    2. 如果不存在负环,则di就是原不等式组的一个可行解

    当然,求最长路亦可,需将原不等式变形为xj≥xi-ck,再将最短路不等式转化为di≥dj+ck,相当于连一条从xi走向xj、长度是-ck的边

  • 求不等式组解的最大值或最小值

    结论:

    1. 如果求的是最小值,则应该求最长路(所有下界的最大值)
    2. 如果求的是最大值,就应该求最短路(所有上界的最小值)

    问题1:如何转化xi≤c,其中c为常数?

    解决1:以有向图为例利用超级源点x0,使xi≤x0+c,然后建立x0—>xi,长度是c

    问题2:如何转化xi-xj=c,其中c为常数?

    解决2:转换为xi-xj≤c和xi-xj≥c

    代码:             

     //求最小值->求最长路
    
    #include
    
    #include
    
    #include
    
    #include
    
    #include
    
    #define _for(i,a,b) for (int i=(a);i<=(b);i++)
    
    using namespace std;
    
    const int N=55,M=1280;
    
    int n,m;
    
    int e[M],ne[M],h[N],w[M],idx;
    
    int d[N],cnt[N];
    
    bitset vis;
    
    inline void c_plus(){
    
           ios::sync_with_stdio(false);
    
           cin.tie(0);
    
           cout.tie(0);
    
    }
    
    inline void init(){
    
           memset(h,-1,sizeof(h));
    
           idx=0;
    
    }
    
    inline void add(int a,int b,int c){
    
           e[idx]=b;
    
           w[idx]=c;
    
           ne[idx]=h[a];
    
           h[a]=idx++;
    
    }
    
    bool spfa(){
    
           memset(d,-1,sizeof(d));//注意:最长路
    
           d[0]=0;
    
           queue q;
    
           q.push(0);
    
           vis[0]=1;
    
           while (!q.empty()){
    
                  int now=q.front();
    
                  q.pop();
    
                  vis[now]=0;
    
                  for (int i=h[now];~i;i=ne[i]){
    
                         int j=e[i];
    
                         if (d[j]n+1){
    
                                       return true;
    
                                }
    
                                if (!vis[j]){
    
                                       vis[j]=1;
    
                                       q.push(j);
    
                                }
    
                         }
    
                  }
    
           }
    
           return false;
    
    }
    
    int main(){
    
           c_plus();
    
           init();
    
           int u,v,W,op;
    
           cin>>n>>m;
    
           while (m--){//op==1:<= op==2:>= op==3 =
    
                  cin>>op>>u>>v>>W;
    
                  if (op==1){
    
                         add(u,v,-W);
    
                  }else if (op==2){
    
                         add(v,u,W);
    
                  }else{
    
                         add(u,v,-W);
    
                         add(v,u,W);
    
                  }
    
           }
    
           _for(i,1,n){
    
                  add(0,i,0);
    
           }
    
           if (spfa()){
    
                  puts("NO");
    
           }else{
    
                  _for(i,1,n){
    
                         cout<<'x'< 
    

    欢迎分享,转载请注明来源:内存溢出

    原文地址: http://outofmemory.cn/zaji/5718536.html

  • (0)
    打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
    上一篇 2022-12-17
    下一篇 2022-12-18

    发表评论

    登录后才能评论

    评论列表(0条)

    保存