题解 P5590 【赛车游戏】

· · 题解

差分约束系统

定义：如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。也就是说，差分约束系统是求解关于一组变量的特殊不等式组的方法

如果还不会差分约束系统的同学请先看差分约束系统的学习笔记

我们来看这个题。题目里说：“随便给边表上一个1...9的长度”，所以对于每一对给定的边(u,v)，都必须满足1\le dis[v]-dis[u] \le9的约束，这样就可以构建差分约束系统了。

由于题目求的是变量差的最小值，所以我们把所有不等式都转化成u-v \ge c的形式，再构图求最长路。具体的构建方式就是：对于每一对边(u,v)，肯定有1\le dis[v]-dis[u] \le9，故从u到v建一条长度为1的有向边，从v到u建一条长度为-9的有向边。

当然，上面只是理论建边方式。由于要求最长路，如果仅仅把spfa松弛时的大于号改了，那岂不是任出题人随便卡？因此，我们在建边时把权值都取相反数，在spfa完后再对dis数组里的每个值去相反数。

如果在差分约束系统上存在负环，那么一定不可解，及时return并输出-1。

本来这样就可以做完了，但是，遗憾的是，这个题可能有一些不必要的点，比如这个图里的2和4点：

由于2点和4点都不会被从1到n的路径经过，所以如果我们还要把他们的约束条件加到约束方程组里，我们的答案就会被不必要的约束所约束，是会得到一个错误的答案的。所以我建了正图和反图，在正图上从1到n跑DFS，在反图上从n到1跑DFS，找出两次都遍历到的点并建新图存下来，然后在新图上构建差分约束系统。

注意判断从1到n是否连通！

以下是代码：

#include<cmath>
#include<queue>
#include<cstdio>
#include<iostream>
const int maxn=4010;
using namespace std;
inline int read()
{
    int fu=1,x=0;char o=getchar();
    while(o<'0'||o>'9'){if(o=='-')fu=-1;o=getchar();}
    while(o>='0'&&o<='9'){x=(x<<1)+(x<<3)+(o^48);o=getchar();}
    return x*fu;
}
struct Edge
{
    int from,to,dis,nst;
}e1[maxn],e2[maxn],edge[maxn];
int n,m,a,b;
int cnt1,cnt2,cnt;
int dis[maxn],num[maxn],from[maxn],to[maxn],sign[maxn];
bool vis1[maxn],vis2[maxn],vis[maxn];
int head1[maxn],head2[maxn],head[maxn];
inline void add(int a,int b,int c)
{
    edge[++cnt].nst=head[a];
    edge[cnt].to=b;
    edge[cnt].from=a;
    edge[cnt].dis=c;
    head[a]=cnt;
}
inline void add1(int a,int b)
{
    e1[++cnt1].nst=head1[a];
    e1[cnt1].to=b;
    e1[cnt1].from=a;
    head1[a]=cnt1;
}
inline void add2(int a,int b)
{
    e2[++cnt2].nst=head2[a];
    e2[cnt2].to=b;
    e2[cnt2].from=a;
    head2[a]=cnt2;
}
void dfs_forward(int x)
{
    for(int i=head1[x];i;i=e1[i].nst)
    {
        int v=e1[i].to;
        if(vis1[v])continue;
        vis1[v]=1;
        dfs_forward(v);
    }
}
void dfs_reverse(int x)
{
    for(int i=head2[x];i;i=e2[i].nst)
    {
        int v=e2[i].to;
        if(vis2[v])continue;
        vis2[v]=1;
        dfs_reverse(v);
    }
}
bool spfa()
{
    queue <int> q;
    for(int i=1;i<=n;i++)
    dis[i]=1e8,vis[i]=0;
    vis[1]=1;dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;num[u]++;
        for(int i=head[u];i;i=edge[i].nst)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].dis)
            {
                dis[v]=edge[i].dis+dis[u];
                if(num[v]>n)return 0;
                if(!vis[v]){vis[v]=1;q.push(v);}
            }
        }
    }
    return 1;
}
void debug()
{
    for(int i=1;i<=n;i++)
    {
        if(vis1[i])cout<<i<<" ";
    }
    cout<<"\n";
    for(int i=1;i<=n;i++)
    {
        if(vis2[i])cout<<i<<" ";
    }
    cout<<"\n";
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        a=read();b=read();
        add1(a,b);add2(b,a);
    }
    dfs_forward(1);dfs_reverse(n);
    for(int i=1;i<=n;i++)
    if(vis1[i]&&vis2[i])sign[i]=1;
    if(!vis1[n]){printf("-1\n");return 0;}
    sign[1]=1;sign[n]=1;
//  debug();
    for(int i=1;i<=m;i++)
    {
        int u=e1[i].from,v=e1[i].to;
        if(sign[u]&&sign[v])
        {
            add(u,v,-1);add(v,u,9);
        }
    }
    if(!spfa()){printf("-1\n");return 0;}
    for(int i=1;i<=n;i++)dis[i]*=-1;
    printf("%d %d\n",n,m);
    for(int i=1;i<=m;i++)
    {
        int u=e1[i].from,v=e1[i].to;
        printf("%d %d ",u,v);
        if(sign[u]&&sign[v])printf("%d\n",dis[v]-dis[u]);
        else printf("1\n");
    }
    return 0;
}