题解 P5590 【赛车游戏】

· · 题解

这道题刚开始看感觉怎么看都不像是差分约束，仔细观察我们大概分几步做。

首先我们判断一下1不能到达n的情况，显然输出-1

紧接着我们需要判断的是一条边是不是在1-n的路径上出现过，这个我们只需要通过正反向dfs以后判断这条边的两条端点是否能够经过。

然后我们就发现求出必要的边以后就可以差分约束，我们考虑对于dis这个条件差分约束，然后我们考虑的就是dis[v]-dis[u]的关系，必须是在1~9的，这我们就可以直接差分约束了。

然后差分约束完毕以后，如果有负环那么我们直接判定无解即可，反之我们直接输出dis[v]-dis[u]即可。

这个思路比较巧妙，我们可以通过差分约束解决一类看似不是差分约束的标号问题。

具体实现我们先两边dfs，然后判断一下1-n不能联通的情况，然后接着我们讲的做就可以了。

代码：

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=1e3+5,M=2e3+5;
struct Graph{int u,v;}g[M];
struct Edge{int to,w,nxt;}e[M<<1];
int n,m,fst[N],tote,dis[N];bool vis[N],rvis[N];
vector<int>adj[N],radj[N];
void dfs(int u){vis[u]=true;for(auto v:adj[u])if(!vis[v])dfs(v);}
void rdfs(int u){rvis[u]=true;for(auto v:radj[u])if(!rvis[v])rdfs(v);}
void adde(int u,int v,int w){e[++tote]=(Edge){v,w,fst[u]};fst[u]=tote;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),adj[u].pb(v),radj[v].pb(u),g[i]=(Graph){u,v};
    dfs(1);rdfs(n);
    if(!vis[n]){puts("-1");return 0;}
    for(int i=1,u,v;i<=m;i++){
        u=g[i].u;v=g[i].v;
        if(vis[u]&&rvis[v])adde(u,v,9),adde(v,u,-1);
    }
    for(int t=1;t<=n;t++)for(int u=1;u<=n;u++)for(int i=fst[u],v;i;i=e[i].nxt)dis[e[i].to]=min(dis[e[i].to],dis[u]+e[i].w);
    for(int u=1;u<=n;u++)for(int i=fst[u],v;i;i=e[i].nxt)if(dis[e[i].to]>dis[u]+e[i].w){puts("-1");return 0;}
    printf("%d %d\n",n,m);
    for(int i=1,u,v;i<=m;i++){
        u=g[i].u;v=g[i].v;
        if(vis[u]&&rvis[v])printf("%d %d %d\n",u,v,dis[v]-dis[u]);else printf("%d %d 1\n",u,v);
    } 
    return 0;
}