题解 P5590 【赛车游戏】

hl666 · 2019-10-13 20:53:59 · 题解

白天比赛的时候基本上都写出来了，结果判无用边的时候脑抽了一下挂了

然而我还以为是后面写跪了一直在魔调233

首先看到这题我们先日常考虑一些简单的情况，我们来分析一下：

若起点不可达终点则输出-1（题面里之前没加上，可TM坑死人了）

若存在一个点无法从起点到达或者是无法到达终点（比赛的时候脑抽写成且了233）那么这个点就是无用的，可以把它删掉，那么所有与它相连的边都可以随便赋值

然后考虑将剩下的边再建成图，那么此时出现环的话环上一定不合法，因此也可以判掉

那么我们惊喜地发现现在剩下的图已经是个DAG了，并且从起点到每个点的所有路径长度都要相同，那我们按拓扑序逐步转移即可。接下来有两种做法：

第一种是我比赛的时候写的，比较诡异，正确性感觉是对的但是又证明不来

考虑先拓扑排序一遍，求出将边长视为1时从起点到每个点的路径长度区间范围[l_i,r_i]

那么我们考虑化边权为点权，把每个点到它的路径总长作为点权val_i，那么显然每个val_i的取值范围就是[r_i,9\times l_i]

考虑1号点的点权可以定下为0，那么对于接下来的每个点，如果它的前驱点j的点权为val_j，那么它的取值区间应该对[val_j+1,val_j+9]取交

那么我们得出每个点的取值区间后直接在里面随便取一个值即可（顺手取最小值），同时再判掉一些无解的情况

乍一看随便取可能会错，但是这里的后面的点权范围是在前面的路径情况下考虑过的结果，因此可以通过此题

#include<cstdio>
#include<vector>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
typedef vector <int>:: iterator VI;
const int N=2005,INF=1e9;
struct interval
{
    int l,r;
    inline interval(CI L=-INF,CI R=INF)
    {
        l=L; r=R;
    }
    friend inline interval operator & (const interval& A,const interval& B)
    {
        return interval(max(A.l,B.l),min(A.r,B.r));
    }
    inline void operator &=(const interval& ots)
    {
        *this=*this&ots;
    }
}v[N]; int n,m,x[N],y[N],z[N],q[N],val[N];
bool f1[N],f2[N]; vector <int> pre[N];
struct Graph
{
    struct edge
    {
        int to,nxt;
    }e[N]; int head[N],cnt,deg[N];
    inline void clear(void)
    {
        memset(head,0,n+1<<2); memset(deg,0,n+1<<2); cnt=0;
    }
    inline void addedge(CI x,CI y)
    {
        e[++cnt]=(edge){y,head[x]}; head[x]=cnt; ++deg[y];
    }
    #define to e[i].to
    inline void BFS(CI st,bool *vis)
    {
        RI H=0,T=1; vis[q[1]=st]=1; while (H<T)
        {
            int now=q[++H]; for (RI i=head[now];i;i=e[i].nxt)
            if (!vis[to]) vis[to]=1,q[++T]=to;
        }
    }
    inline bool Top_Sort(void)
    {
        RI H=0,T=0,i; for (i=1;i<=n;++i) if (!deg[i]) q[++T]=i;
        while (H<T)
        {
            int now=q[++H]; for (i=head[now];i;i=e[i].nxt)
            if (pre[to].push_back(now),!--deg[to]) q[++T]=to;
        }
        return T==n;
    }
    #undef to
}A,B;
int main()
{
    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
    RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
    scanf("%d%d",&x[i],&y[i]),A.addedge(x[i],y[i]),B.addedge(y[i],x[i]);
    for (A.BFS(1,f1),B.BFS(n,f2),i=1;i<=m;++i) if (!f1[x[i]]||!f2[x[i]]) z[i]=1;
    if (!f1[n]) return puts("-1"),0;
    for (A.clear(),i=1;i<=m;++i) if (!z[i]) A.addedge(x[i],y[i]);
    if (!A.Top_Sort()) return puts("-1"),0; for (v[1]=interval(0,0),i=2;i<=n;++i)
    {
        int mi=INF,mx=-INF; for (VI it=pre[q[i]].begin();it!=pre[q[i]].end();++it)
        mi=min(mi,v[*it].l+1),mx=max(mx,v[*it].r+1); v[q[i]]=interval(mi,mx);
    }
    for (i=1;i<=n;++i) if (v[i]=interval(v[i].r,9*v[i].l),v[i].l>v[i].r)
    return puts("-1"),0; for (i=2;i<=n;++i)
    {
        interval tp; for (VI it=pre[q[i]].begin();it!=pre[q[i]].end();++it)
        tp&=interval(val[*it]+1,val[*it]+9); v[q[i]]&=tp;
        if (v[q[i]].l>v[q[i]].r) return puts("-1"),0; val[q[i]]=v[q[i]].l;
    }
    for (i=1;i<=m;++i) if (!z[i]) z[i]=val[y[i]]-val[x[i]];
    for (printf("%d %d\n",n,m),i=1;i<=m;++i) printf("%d %d %d\n",x[i],y[i],z[i]);
    return 0;
}

当然还有另一种更简单正确性也有保证的做法，我们考虑直接顺推每个点的权值区间，那么此时这个点的取法就会影响到后面了，因此我们可以倒着再做一遍，这样就可以保证正确性

#include<cstdio>
#include<vector>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
typedef vector <int>:: iterator VI;
const int N=2005,INF=1e9;
struct interval
{
    int l,r;
    inline interval(CI L=-INF,CI R=INF)
    {
        l=L; r=R;
    }
    friend inline interval operator & (const interval& A,const interval& B)
    {
        return interval(max(A.l,B.l),min(A.r,B.r));
    }
    inline void operator &=(const interval& ots)
    {
        *this=*this&ots;
    }
}v[N]; int n,m,x[N],y[N],z[N],q[N],val[N];
bool f1[N],f2[N]; vector <int> pre[N];
struct Graph
{
    struct edge
    {
        int to,nxt;
    }e[N]; int head[N],cnt,deg[N];
    inline void clear(void)
    {
        memset(head,0,n+1<<2); memset(deg,0,n+1<<2); cnt=0;
    }
    inline void addedge(CI x,CI y)
    {
        e[++cnt]=(edge){y,head[x]}; head[x]=cnt; ++deg[y];
    }
    #define to e[i].to
    inline void BFS(CI st,bool *vis)
    {
        RI H=0,T=1; vis[q[1]=st]=1; while (H<T)
        {
            int now=q[++H]; for (RI i=head[now];i;i=e[i].nxt)
            if (!vis[to]) vis[to]=1,q[++T]=to;
        }
    }
    inline bool Top_Sort(void)
    {
        RI H=0,T=0,i; for (i=1;i<=n;++i) if (!deg[i]) q[++T]=i;
        while (H<T)
        {
            int now=q[++H]; for (i=head[now];i;i=e[i].nxt)
            if (pre[to].push_back(now),!--deg[to]) q[++T]=to;
        }
        return T==n;
    }
    #undef to
}A,B;
int main()
{
    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
    RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
    scanf("%d%d",&x[i],&y[i]),A.addedge(x[i],y[i]),B.addedge(y[i],x[i]);
    for (A.BFS(1,f1),B.BFS(n,f2),i=1;i<=m;++i) if (!f1[x[i]]||!f2[x[i]]) z[i]=1;
    if (!f1[n]) return puts("-1"),0;
    for (A.clear(),i=1;i<=m;++i) if (!z[i]) A.addedge(x[i],y[i]);
    if (!A.Top_Sort()) return puts("-1"),0; v[1]=interval(0,0);
    for (i=2;i<=n;++i) for (VI it=pre[q[i]].begin();it!=pre[q[i]].end();++it)
    v[q[i]]&=interval(v[*it].l+1,v[*it].r+9);
    for (i=n;i>1;--i) for (VI it=pre[q[i]].begin();it!=pre[q[i]].end();++it)
    v[*it]&=interval(v[q[i]].l-9,v[q[i]].r-1);
    for (i=1;i<=n;++i) if (v[i].l>v[i].r) return puts("-1"),0;
    for (i=1;i<=m;++i) if (!z[i]) z[i]=v[y[i]].l-v[x[i]].l;
    for (printf("%d %d\n",n,m),i=1;i<=m;++i) printf("%d %d %d\n",x[i],y[i],z[i]);
    return 0;
}