題目：

 不難看出題意主要是給出ml+md個格式為xi-xj<=ak的不等式，xi-xj為i，j倆頭牛的距離，要我們求x1-xn的最大值，

經過上下加減我們可以將這幾個不等式化成x1-xn<=a1+a2+a3+a4+....+ak,在這加減的程序中我們不難看到dijstra的身影，這加加減減的程序不正是松弛操作嗎！

這時我們就得到了正解——差分約束演算法，此演算法主要用于處理差分約束系統：如果一個系統由n個變數和m個約束條件組成，形成m個形如ai-aj≤k的不等式(i,j∈[1,n],k為常數),則稱其為差分約束系統，

結論：求解差分約束系統，都可以轉化成圖論的單源最短路徑（或最長路徑）問題，

關于差分約束與最短路模型的關系

我們觀察上面例子中的不等式，都是x[i] - x[j] <= a[k]，可以進行移項，成為x[i] <= x[j] + a[k]，我們令a[k] = w(j, i)，dis[i]=x[i],并使i=v,j=u,那么原始就變為：dis[u]+w(u,v)>=dis[v],于是可以聯想到最短路模型中的一部分代碼

if(dis[u]+w(u,v)<=dis[v])
{
    dis[v]=dis[u]+w(u,v);
}

這不正與松弛操作相似嗎？

但是好像不等號方向剛好相反，但其實這并不矛盾

上面的代碼要實作的是使dis[u]+w(u,v)>dis[v],而對于不等式，我們進行建邊的操作：對于每個不等式 x[i] - x[j] <= a[k]，對結點 j 和 i 建立一條 j -> i的有向邊，邊權為a[k]，求x[n-1] - x[0] 的最大值就是求 0 到n-1的最短路，兩者剛好吻合，所以求解差分約束問題就轉化為了最短路問題，

問題解的存在性

由于在求解最短路時會出現存在負環或者終點根本不可達的情況，在求解差分約束問題時同樣存在

（1）存在負環

如果路徑中出現負環，就表示最短路可以無限小，即不存在最短路，那么在不等式上的表現即X[n-1] - X[0] <= T中的T無限小，得出的結論就是 X[n-1] - X[0]的最大值不存在，在SPFA實作程序中體現為某一點的入隊次數大于節點數，（貌似可以用sqrt(num_node)來代替減少運行時間）

（2）終點不可達

這種情況表明X[n-1]和X[0]之間沒有約束關系，X[n-1] - X[0]的最大值無限大，即X[n-1]和X[0]的取值有無限多種，在代碼實作程序中體現為dis[n-1]=INF，

參考的文章鏈接：https://blog.csdn.net/my_sunshine26/article/details/72849441

注意

1.因為本題中可能存在負權環（眾所周知dijstra在碰到這個玩意時完全沒有辦法）所以我們需要用到SPFA

2.后md個不等式題目一開始給的是：xj-xi>=a 我們可以推出xi-xj<=-a（這在之后的建圖處理中會用到）注意負權邊，

3.題目所給的條件不一定是對的，所以我們需要跑兩次SPFA判斷圖是不是聯通的，（因為洛谷上有3個坑逼資料）

代碼：

此為沒有考慮條件不正確的情況的代碼，70分（洛谷上），在聯賽是應該是100分的

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N=1005;
const int M=40005;
int n,ml,md;
struct EDGE{
    int next,to,w;
}edge[M];
int head[N],tot;
void add(int x,int y,int v){
    edge[++tot].next=head[x];
    edge[tot].to=y;
    edge[tot].w=v;
    head[x]=tot;
}
queue<int> q;
int vis[N],dis[N],circle[N];//circle為指向tt的個數 
void spfa(int s){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(circle,0,sizeof(circle));
    q.push(s);
    vis[s]=1,dis[s]=0;
    while(!q.empty()){
        int now=q.front(); 
		q.pop(); 
		vis[now]=0;
        for(int i=head[now];i;i=edge[i].next){
            int tt=edge[i].to;
            if(dis[now]+edge[i].w<dis[tt]){
                dis[tt]=dis[now]+edge[i].w;
                circle[tt]=circle[now]+1;
                if(circle[tt]>=n){//指向tt的邊超過n個自然是不滿足條件的 
                    puts("-1");exit(0);
                }
                if(!vis[tt]){
                    vis[tt]=1;
                    q.push(tt);
                }
            }
        }
    }

}
int main(){
    scanf("%d%d%d",&n,&ml,&md);
    for(int i=1;i<=ml;i++){
    	int a,b,d; 
        scanf("%d%d%d",&a,&b,&d);
        add(a,b,d);//a-b<=d
    }
    for(int i=1;i<=md;i++){
    	int a,b,d;
        scanf("%d%d%d",&a,&b,&d);
        add(b,a,-d);//b-a>=d ==> a-b<=-d
    }
    spfa(1);
    if(dis[n]>1e8){puts("-2");return 0;} 
    printf("%d",dis[n]);
    return 0;
}

AC代碼

#include<bits/stdc++.h>
using namespace std;
int n,ml,md,a,b,c,fst[10100],nex[50010],v[50010],w[50010],cnt,vis[10100],dis[10100],tim[10100];
queue<int> q;
void add(int a,int b,int c)
{
    nex[++cnt]=fst[a];
    fst[a]=cnt;
    v[cnt]=b;
    w[cnt]=c;
    return ;
}
int spfa(int k)
{
    memset(dis,0x7f/3,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(tim,0,sizeof(tim));
    q.push(k);
    dis[k]=0;
    vis[k]=1;
    while(!q.empty())
    {
        int u=q.front();
        //cout<<u<<" ";
        q.pop();
        tim[u]++;
        vis[u]=0;
        if(tim[u]>n)
        return -1;
        for(int i=fst[u];i!=-1;i=nex[i])
        {
            if(dis[v[i]]>dis[u]+w[i])
            {
                dis[v[i]]=dis[u]+w[i];
                if(!vis[v[i]])
                {
                    q.push(v[i]);
                    vis[v[i]]=1;
                }
            }
        }
    }
    /*cout<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<" ";
    }*/
    if(dis[n]>1e8)
    return -2;
    return dis[n];
}
int main()
{
    memset(fst,-1,sizeof(fst));
    cin>>n>>ml>>md;
    for(int i=1;i<=ml;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    for(int i=1;i<=md;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(b,a,-c);
    }
    for(int i=1;i<n;i++)
    {
        add(i+1,i,0);
    }
    for(int i=1;i<=n;i++)
    {
        add(0,i,0);
    }
    int sp=spfa(0); 
    if(sp<=-1)
    {
        cout<<sp;
        return 0;
    }
    else
    {
        cout<<spfa(1);
    }
    //cout<<" "<<sp;
    return 0;
}

代碼參考：https://www.luogu.org/blog/roy1994/solution-p4878  https://www.luogu.org/blog/mikasamikasa/solution-p4878

標籤：其他

上一篇：計算及校驗海明碼的3個舉例

下一篇：希爾排序