P5590 赛车游戏

· · 题解

题意分析

给你一张有向图，让你给图上的边赋边权，边权的范围为[1,9]，使得1到n的所有路径等长

思路解析

既然题目说了路径等长，那不开一个数组存储路径长度不是很亏吗？ 所以我们定义一个数组d存储节点1到每个节点的路径长度。根据题意，边权的范围为[1,9]，因此对于图中的所有有向边(u,v)，在有解的情况下，有以下式子：

1\leq d[v]-d[u]\leq 9

草， 一眼看上去就长得一副差分约束的亚子。等等，SPFA…… 看一眼数据范围，嗯，没毛病，就它了！无耻地安利一波博客：差分约束系统详解

现在考虑什么时候无解。显然，当路径存在环时，肯定是无解的，因为边权范围是[1,9]，经过环的路径长度一定是比不经过环的长的，而题目要求路径长度相同，因此此时无解。然而不判也可以过。 差分约束无解就不多说了，判负环就完事了。

具体实现

怎么建差分约束系统呢？暴力 一遍dfs，判断该边是否在1到n的路径上，如果在，就按照上面的关系式建边，即从u向v连一条边权为9的边，从v向u连一条边权为-1的边。

但是，看了一眼数据范围（刚刚不是看过了吗），发现虽然SPFA活了，暴力还是苟延残喘，实测60pts，100%的数据只过了无解的2个点。因此要进行一个剪枝。

显然，在有解的图上是不存在环的。因此，可以存储一个节点能否到达n节点，如果能，就不用继续走，直接返回。

最后还有一个问题，差分约束条件是针对路径上的边，因为之前我们没有对不在路径上的边进行约束，因此这些边的边权可能不在[1,9]的范围内。然而这些边毫无用处，边权只要在范围内就可以了，因此我们随便给它们赋一个值就行。欢迎rand

这样这题就解完了！

最后奉上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int N=1e4,M=1e5;
int n,m,tot,tot1;
int head[N],ver[M],Next[M];
int h1[N],v1[2*M],n1[2*M],e1[2*M];
int x[N],y[N],d[N],cnt[N];
bool v[N],p[N];
queue<int> q;
void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}//原图
void Add(int x,int y,int z)
{
    v1[++tot1]=y,e1[tot1]=z,n1[tot1]=h1[x],h1[x]=tot1;
}//差分约束系统图
bool spfa()
{
    memset(v,0,sizeof(v));
    memset(d,0x3f,sizeof(d));
    queue<int> q;
    q.push(0);
    d[0]=0,v[0]=1;
    while(q.size())
    {
        int x=q.front();q.pop();v[x]=0;
        for(int i=h1[x];i;i=n1[i])
            if(d[x]+e1[i]<d[v1[i]])
            {
                int y=v1[i];
                d[y]=d[x]+e1[i];
                cnt[y]=cnt[x]+1;
                if(cnt[y]>n)
                    return 1;//存在负环，无解
                if(!v[y])
                {
                    q.push(y);
                    v[y]=1;
                }
            }
    }
    return 0;
}//差分约束
bool dfs(int x)
{
    if(x==n || p[x])
        return 1;//到达n节点以及剪枝
    for(int i=head[x];i;i=Next[i])
        if(!v[i])
        {
            v[i]=1;
            if(dfs(ver[i]))//如果能够到达n节点，即在路径上
            {
                Add(x,ver[i],9),Add(ver[i],x,-1);//建边
                p[x]=1;
            }
        }
    return p[x];
}//建立差分约束系统
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        add(x[i],y[i]);
    }
    for(int i=1;i<=n;i++)
        Add(0,i,0);
    if(!dfs(1) || spfa())
    {
        puts("-1");
        return 0;
    }//不存在路径和无解直接输出
    printf("%d %d\n",n,m);
    for(int i=1;i<=m;i++)
    {
        printf("%d %d ",x[i],y[i]);
        int now=abs(d[x[i]]-d[y[i]]);
        if(now>0 && now<10)
            printf("%d\n",now);//在范围内直接输出
        else
            puts("1");//不在范围内一定不在路径上，随便赋值1~9
    }
    return 0;
}