差分约束 USACO2005 Layout

今早在学习最短路的时候在做USACO2005的布局。

我做此题的经历

百思(……)不得其解。因为知道它是最短路问题,所以我就乱来了,直接认为那个不等式右边的就是长度。在mspaint.exe上画了几下样例,发现其实要求最大距离,喜欢的牛是对后面有约束的,而不喜欢的牛是对前面有约束的。就是说,把这些牛排队想象成一个动态的过程,为了保证最后面的那个牛能够到最远的距离,所有的牛都要往后面挤,对于每一个牛,“我”不能继续往后只有两个原因:前面有我喜欢的牛,而且后面有我讨厌的牛。所以我把第i头牛距离第1头牛的距离设为d[i],把它们横过来看,也就是横坐标的值,其中第一头牛的横坐标的值为0.从第一头牛开始,每次通过约束条件和当前牛的横坐标约束一下更新一下另外一个点的横坐标,如果更新了的话,就把它加入更新队列。这其实就得到了SPFA,只不过是求最长路的SPFA:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
queue<int>q;
vector<int>con[1010],w[1010];
int d[1010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(d,-1,sizeof(d));
    int n,ml,md,cur,a,b,x;
    cin>>n>>ml>>md;
    while(ml--){
        cin>>a>>b>>x;
        con[a].push_back(b);
        w[a].push_back(x);
    }
    while(md--){
        cin>>a>>b>>x;
        con[b].push_back(a);
        w[b].push_back(-x);
    }
    d[1]=0;
    q.push(1);
    while(!q.empty()){
        cur=q.front();
        q.pop();
        for(int i=0;i<con[cur].size();i++){
            if(d[con[cur][i]]<d[cur]+w[cur][i]){
                d[con[cur][i]]=d[cur]+w[cur][i];
                q.push(con[cur][i]);
            }
        }
    }
    cout<<d[n];
}

评测结果:AMTMTTWTTM

其实我已经猜到了结果了。但是通过提交,可以发现问题主要存在于没有判断-1和-2的两种特殊情况。另外我看了一下在CodeVS上题目的分类,最短路,应该是要用最小值啊?虽然不明不白,但是改成最短路,再加上无限远的判断(-2):

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
queue<int>q;
vector<int>con[1010],w[1010];
int d[1010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,ml,md,cur,a,b,x;
    cin>>n>>ml>>md;
    while(ml--){
        cin>>a>>b>>x;
        con[a].push_back(b);
        w[a].push_back(x);
    }
    while(md--){
        cin>>a>>b>>x;
        con[b].push_back(a);
        w[b].push_back(-x);
    }
    d[1]=0;
    for(int i=2;i<=n;i++){
        d[i]=2147483647;
    }
    q.push(1);
    while(!q.empty()){
        cur=q.front();
        q.pop();
        for(int i=0;i<con[cur].size();i++){
            if(d[con[cur][i]]>d[cur]+w[cur][i]){
                d[con[cur][i]]=d[cur]+w[cur][i];
                q.push(con[cur][i]);
            }
        }
    }
    if(d[n]==2147483647){
        cout<<-2;
    }else{
        cout<<d[n];
    }
}

评测结果:AATAAAAAAA

Excuse me?我乱来的竟然都已经过了9个点了?再蒙一个,SPFA判断回路的方法是判断入队次数是否超过n。这个判断在SPFA中是非常好理解的,但是在这道题中不怎么想得明白。但是CodeVS上是不计AC率的,所以多提交几次都没关系:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
queue<int>q;
vector<int>con[1010],w[1010];
int d[1010],in[1010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(in,0,sizeof(in));
    int n,ml,md,cur,a,b,x;
    cin>>n>>ml>>md;
    while(ml--){
        cin>>a>>b>>x;
        con[a].push_back(b);
        w[a].push_back(x);
    }
    while(md--){
        cin>>a>>b>>x;
        con[b].push_back(a);
        w[b].push_back(-x);
    }
    d[1]=0;
    for(int i=2;i<=n;i++){
        d[i]=2147483647;
    }
    q.push(1);
    while(!q.empty()){
        cur=q.front();
        q.pop();
        in[cur]++;
        if(in[cur]>n){
            cout<<-1;
            return 0;
        }
        for(int i=0;i<con[cur].size();i++){
            if(d[con[cur][i]]>d[cur]+w[cur][i]){
                d[con[cur][i]]=d[cur]+w[cur][i];
                q.push(con[cur][i]);
            }
        }
    }
    if(d[n]==2147483647){
        cout<<-2;
    }else{
        cout<<d[n];
    }
}

评测结果:AAAAAAAAAA

于是我随便试了一组自己出的数据:

3 1 1
1 3 20
1 2 40

运行结果:

40

但是从输入的数据上来看,这个情况应该是不存在的。这只能说明,CodeVS的数据比较弱。

为了解决这种情况,我把编号大的一定在编号小的前面这种情况统一当成奶牛讨厌的情况来处理。这才应该是正确的程序:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
queue<int>q;
vector<int>con[1010],w[1010];
int d[1010],in[1010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(in,0,sizeof(in));
    int n,ml,md,cur,a,b,x;
    cin>>n>>ml>>md;
    while(ml--){
        cin>>a>>b>>x;
        con[a].push_back(b);
        w[a].push_back(x);
    }
    while(md--){
        cin>>a>>b>>x;
        con[b].push_back(a);
        w[b].push_back(-x);
    }
    d[1]=0;
    for(int i=2;i<=n;i++){
        d[i]=2147483647;
        con[i].push_back(i-1);//加了这两句
        w[i].push_back(0);
    }
    q.push(1);
    while(!q.empty()){
        cur=q.front();
        q.pop();
        in[cur]++;
        if(in[cur]>n){
            cout<<-1;
            return 0;
        }
        for(int i=0;i<con[cur].size();i++){
            if(d[con[cur][i]]>d[cur]+w[cur][i]){
                d[con[cur][i]]=d[cur]+w[cur][i];
                q.push(con[cur][i]);
            }
        }
    }
    if(d[n]==2147483647){
        cout<<-2;
    }else{
        cout<<d[n];
    }
}

差分约束

我在网上搜索了这道题之后,发现这道题事实上应该使用差分约束[1]来做。

现在我来说说我的理解吧。差分约束事实上是一个多元不等式组,每一个不等式都形如yxky-x\leq k,这样的不等式可以等价于有向图中x到y的距离。这样的等价是非常有用的。举例说明,有一个不等式组:

b-a≤k1 对应 w[a->b]=k1
c-b≤k2 对应 w[b->c]=k2
d-c≤k3 对应 w[c->d]=k3
e-d≤k4 对应 w[d->e]=k4

把上面几个东西相加得到e-a≤k1+k2+k3+k4 对应 w[a->e]=k1+k2+k3+k4!多么的精巧!

那么我们可能想要求某一些相减关系的最大值。不妨设这两个数为m、n,求m-n的最大值。那么我们只要求出与m-n有关的不等式就好了。假设求出来的几个不等式(路径)中有:

m-n≤k1
m-n≤k2
m-n≤k3

为了求出m-n的最大值,我们需要解出上面的不等式组。我们都知道,上面不等式组的解为m-n≤min{k}=min{w[m->n]},惊讶的发现,这就是最短路!后面再愉快地SPFA,bellman-ford,dijkstra,想怎么求怎么求。

在这题上的应用

还是和我上面一样,设d[i]为第i头牛的横坐标。

第A、B头牛互相喜欢(假设A≤B),距离最多为D,就等价于d[B]-d[A]≤D。这里不需要考虑d[A]-d[B]≤D是因为d[A]≤d[B],这是必然成立的,多加一条边会拖慢时间而且没有什么用。

第A、B头牛互相讨厌(假设A≤B),距离至少为D,则等价于d[B]-d[A]≥D,变形一下,两边同乘以-1,得d[A]-d[B]≤-D,这时候只要添加一条从B到A的负权边就好了。

还有一个限制条件就是说当A≤B时,d[A]≤d[B],因为奶牛是按次序排队的。

然后跑一边SPFA,假如出现了负环,说明这种排列不可能。假如跑完了SPFA之后d[n]还是为INF,则说明1号牛和n号牛之间的距离可以为无限大。

这题就是这样了。

思考延伸

我想了一下好像不怎么能拓展这种类型的题目,系数变一下,变量个数变一下,都不再满足这些性质。这么巧妙的构思,总感觉可以有别的应用。


  1. http://www.cnblogs.com/void/archive/2011/08/26/2153928.html

avatar
Kerry Su