题解 P5590 【赛车游戏】

mzgwty · 2019-10-14 14:10:03 · 题解

话说月赛怎么出原题了......继3月月赛后再出原题

这题和CF241E很像，只是那题要求每条边的权值要么是1要么是2罢了。

但作者考场上总会出一些意外的状况，比如被叫去吃饭之类的，所以考场写了个大暴力，一分都没有。

经过某个神仙 @Social_Zhao 指点后，发现了这是差分约束......

对于每一条边，权值≤9，≥1，所以就有

即dis_{to}-dis_{from}<=9且dis_{from}-dis_{to}<=-1

然后这就是一个明显的差分约束了。

从from到to连一条权值为-1的边，再从to到from连一条权值为9的边。从1跑spfa,有负环输出-1,否则对于每一条边，权值等于dis_{to}-dis_{from}

但是，有一些坑点

坑点一

比如这个图（脑补一下，点不开作图工具）

显然，你直接跑差分约束是会挂掉的，因为图里从1出发有负环。但是从1到n(即12)仅有一条路径，所以肯定是有解的。

那么我们应该怎么办呢？

显然，只需要把不在1到n的路径上的点和边全部不管，再跑差分约束即可。对于不在指定路径上的边，直接把它们的权值赋为1-9的任意整数即可。

对于处理无用点，一般使用两遍dfs/bfs,一遍用原边从1遍历；另一遍用反向边，从n遍历，两次都遍历到的点就在1->n的路径上。

坑点二

必须要判断1->n是否联通，不然你会得到30分的高分

讲完了QWQ

#include<bits/stdc++.h>
#include<queue>
#define R register
#define rep(i,a,b) for(R int i=a ; i<=b ; ++i)
#define dwn(i,a,b) for(R int i=a ; i>=b ; --i)
using namespace std;

inline int read() {
    int res=0,f=1;char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
    do {
        res=res*10+ch-'0';
    } while(isdigit(ch=getchar()));
    return res*f;
}

const int N=2005;

struct Edge {
    int next,from,to,val;
}a[N<<1],b[N<<1],c[N<<1];

int head[N],tail[N],size;

bool ok1[N],ok2[N],ok[N];

inline void add(int u,int v) {
    a[++size].next=head[u],a[size].from=u,a[size].to=v,head[u]=size;
    b[size].next=tail[v],b[size].to=u,tail[v]=size;
}

void dfs1(int u) {
    ok1[u]=1;
    for(R int i=head[u] ; i ; i=a[i].next) {
        int v=a[i].to;
        if(!ok1[v]) dfs1(v);
    }
}

void dfs2(int u) {
    ok2[u]=1;
    for(R int i=tail[u] ; i ; i=b[i].next) {
        int v=b[i].to;
        if(!ok2[v]) dfs2(v);
    }
}

inline void add2(int u,int v,int w) {
    c[++size].next=head[u],c[size].to=v,c[size].val=w,head[u]=size;
}

int dis[N],num[N];

bool inq[N];

int main() {
    int n=read(),m=read();
    rep(i,1,m) {
        int x=read(),y=read();
        add(x,y);
    }
    dfs1(1),dfs2(n);
    rep(i,1,n) ok[i]=ok1[i]&ok2[i];
    size=0,memset(head,0,sizeof(head));
    rep(i,1,m) if(ok[a[i].from]&&ok[a[i].to]) add2(a[i].from,a[i].to,9),add2(a[i].to,a[i].from,-1);
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    queue <int> q;
    q.push(1),num[1]=inq[1]=1;
    while(!q.empty()) {
        int u=q.front();q.pop(),inq[u]=0;
        for(R int i=head[u] ; i ; i=c[i].next) {
            int v=c[i].to;
            if(dis[v]>dis[u]+c[i].val) {
                dis[v]=dis[u]+c[i].val;
                if(!inq[v]) {
                    if(num[v]==n) {
                        printf("-1");
                        return 0;
                    }
                    q.push(v),inq[v]=1,++num[v];
                }
            }
        }
    }
    if(dis[n]==0x3f3f3f3f) {
        printf("-1");
        return 0;
    }
    printf("%d %d\n",n,m);
    rep(i,1,m) {
        printf("%d %d ",a[i].from,a[i].to);
        if(!ok[a[i].from]||!ok[a[i].to]) printf("1");
        else printf("%d",dis[a[i].to]-dis[a[i].from]);
        puts("");
    }
    return 0;
}