csp201809-4

标签：xj xk int 305 Sj csp201809 dis

这是一道差分约束求最长路的图的问题：

通过已知的条件可以容易列出以下不等式：

2*a1<=x1+x2<=2*a1+1

3*a2<=x1+x2+x3<=3*a2+2

3*a3<=x2+x3+x4<=3*a3+2

                .......

3*an-1<=xn-2+xn-1+xn<=3*an-1+2

2*an<=xn-1+xn<=2*an+1

以及xn>=1

我们可以通过一些简单的移项将其变成：

xi+xk>=num1  ; -xi-xk>=-num2        

或者

xi+xj+xk>=num1 ；  -（xi+xj+xk）>=-num2

可以定义Sj=x0+x1+....xj，那么就可以转换为：

Sj-Si>=num的状态，其几何含义为从i点到j点的长度最小为num

想要求得x的最小值，那么就需要求得num的最大值，由此转换为求图的最长路的问题，鉴于其存在负权路，那么使用SPFA最好。

#include<bits/stdc++.h>
using namespace std;
int a[305];
int dis[305];
int vis[305];
vector<pair<int,int>>G[305];
int n;
void SPFA(){//存在负权求最长路
    for(int i=0;i<=n;i++){dis[i]=0,vis[i]=0;}
    vis[0]=1;
    queue<int> p;
    p.push(0);
    while(!p.empty()){
        int now=p.front();p.pop();
        for(int i=0;i<G[now].size();i++){
            if(dis[G[now][i].first]<dis[now]+G[now][i].second){
                dis[G[now][i].first]=dis[now]+G[now][i].second;
                if(vis[G[now][i].first]!=1){
                    p.push(G[now][i].first);
                }
            }
        }
        vis[now]=0;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<=n;i++){
        G[0].push_back({i,0});//超级源点
    }
    for(int i=0;i<n;i++){
        G[i].push_back({i+1,1});//x大于0
    }
    G[0].push_back({2,2*a[1]});
    G[2].push_back({0,-2*a[1]-1});
    G[n-2].push_back({n,2*a[n]});
    G[n].push_back({n-2,-2*a[n]-1});
    for(int i=2;i<=n-1;i++){
        G[i-2].push_back({i+1,3*a[i]});
        G[i+1].push_back({i-2,-3*a[i]-2});
    }
    SPFA();
    for(int i=1;i<=n;i++){
        cout<<dis[i]-dis[i-1]<<" ";
    }
}

超级源点的使用是防止图不连通，其另一个作用是初始化最长路为0。

那么Sj就是超级源点到j点的最长路dis[j]了，求出xj的方法就是Sj-Sj-1=dis[j]-dis[j-1]

代码AC

 

标签：xj,xk,int,305,Sj,csp201809,dis
From： https://www.cnblogs.com/yds0823/p/17177327.html