【洛谷P5590】赛车游戏 | Mrsrz's blog

差分约束

题目大意：

给定一张简单有向图。要给每条边添加 $[1,9]$ 中的整数权值，使得所有 $1$ 到 $n$ 的路径的长度都相等。

题解：

考虑 $d_i$ 表示从 $1$ 到 $i$ 的路径长度。那么我们只需得到一组合法的 $d_i$，然后有边相连的两点 $u\rightarrow v$ 之间的边权就为 $d_v-d_u$。

由限制条件可得，存在 $u\rightarrow v$ 的边时，$1\leq d_v-d_u\leq 9$。

拆开来，$d_v-d_u\geq 1$ 和 $d_v-d_u\leq 9$。

转化一下得 $d_u\leq d_v-1$ 和 $d_v\leq d_u+9$。

容易想到差分约束模型，跑 SPFA 求出一组解即可。

如果出现负环或两点不连通则为无解。

如果负环出现在无法到达 $n$ 的路径上，则并不会有影响，这些边随便标即可。

时间复杂度 $O(nm)$。

Code：

#include<iostream>
#include<vector>
#include<queue>
const int N=2333,inf=1e9;
using namespace std;
vector<int>G[N];
int n,m,head[N],cnt,dis[N],iq[N];
pair<int,int>E[N];
bool ok[N],vis[N];
struct edge{
    int to,nxt,dis;
}e[N<<1];
int get(int now){
    if(ok[now])return 1;
    vis[now]=1;
    for(int to:G[now])
        if(!vis[to])
            ok[now]|=get(to);
    vis[now]=0;
    return ok[now];
}
inline void addedge(int u,int v,int w){
    e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
}
queue<int>q;
bool spfa(){
    for(int i=2;i<=n;++i)dis[i]=inf;
    for(q.push(1);!q.empty();){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
            if(dis[e[i].to]>dis[u]+e[i].dis){
                dis[e[i].to]=dis[u]+e[i].dis;
                if(!vis[e[i].to]){
                    if(++iq[e[i].to]>=n)return 0;
                    vis[e[i].to]=1;
                    q.push(e[i].to);
                }
            }
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        E[i]=make_pair(u,v);
    }
    ok[n]=1;
    ok[1]=get(1);
    if(!ok[1]){
        cout<<"-1\n";
        return 0;
    }
    for(int f=1;f<=n;++f)
        for(int to:G[f])
            if(ok[f]&&ok[to])
                addedge(f,to,9),addedge(to,f,-1);
    if(!spfa()){
        cout<<"-1\n";
        return 0;
    }
    cout<<n<<' '<<m<<'\n';
    for(int i=1;i<=m;++i){
        int u=E[i].first,v=E[i].second;
        if(dis[v]==inf||dis[u]==inf)cout<<u<<' '<<v<<" 6\n";
        else
            cout<<u<<' '<<v<<' '<<dis[v]-dis[u]<<'\n';
    }
    return 0;
}