题解 P5590 【赛车游戏】

Nemlit

2019-10-13 23:31:01

Solution

~~果然我还是太$Naive$了~~ 首先有一些点/边其实是没有意义的,如果从1出发不能到该点或者从该点不能到n,这个点就可以不用管了。这个过程可以用正反两边$dfs/bfs$实现 然后删掉那些点之后,新图中如果出现了环,那么显然是无解的 然后现在图就转化成了一张$DAG$ 由于$1->n$的所有路径是定值,那么$1->$新图中所有点的路径都应该是一个定值(反证一下就知道了) 然后我们发现,对于每一条边$u->v$,实际上是要满足$1≤dis_v - dis_u ≤ 9$,不难发现这是一个**差分约束**模型 移一下项,我们有:$dis_u+1≤dis_v$,$dis_v-9≤dis_u$ 于是对于每一条边$(u, v)$,我们连一条$(u, v, 1)$和一条$(u, v, -9)$即可 ## $Code:$ ~~不知道为什么只有30,先咕一会,调出来再放~~ ~~好了调出来了,不连通的那些边的终点起点忘记输出了~~ ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define _ 20005 int n, m, head1[_], cnt, head2[_], head3[_], vis[_], dis[_], num[_], pax[_], v1[_], v2[_]; struct edge { int u, v, w, next; }e1[_], e2[_], e3[_ << 1]; il void add1(int u, int v) { e1[++ cnt] = (edge){u, v, 0, head1[u]}, head1[u] = cnt; e2[cnt] = (edge){v, u, 0, head2[v]}, head2[v] = cnt; } il void add2(int u, int v) { e3[++ cnt] = (edge){u, v, 1, head3[u]}, head3[u] = cnt; e3[++ cnt] = (edge){v, u, -9, head3[v]}, head3[v] = cnt; } il void dfs1(int u) { v1[u] = 1; for(re int i = head1[u]; i; i = e1[i].next) if(!v1[e1[i].v]) dfs1(e1[i].v); } il void dfs2(int u) { v2[u] = 1; for(re int i = head2[u]; i; i = e2[i].next) if(!v2[e2[i].v]) dfs2(e2[i].v); } queue<int>q; il void SPFA() { memset(dis, -64, sizeof(dis)), q.push(1), dis[1] = 0; while(!q.empty()) { int u = q.front(); q.pop(), vis[u] = 0; for(re int i = head3[u]; i; i = e3[i].next) { int v = e3[i].v; if(dis[v] < dis[u] + e3[i].w) { dis[v] = dis[u] + e3[i].w; if(!vis[v]) q.push(v), vis[v] = 1, ++ num[v]; if(num[v] > n) puts("-1"), exit(0); } } } } int main() { n = read(), m = read(); rep(i, 1, m) { int u = read(), v = read(); add1(u, v); } dfs1(1), dfs2(n), cnt = 0; if(!v1[n]) return puts("-1"), 0; rep(i, 1, n) if(v1[i] && v2[i]) pax[i] = 1; rep(i, 1, m) if(pax[e1[i].u] && pax[e1[i].v]) add2(e1[i].u, e1[i].v); SPFA(), printf("%d %d\n", n, m); rep(i, 1, m) { if(pax[e1[i].u] && pax[e1[i].v]) { printf("%d %d %d\n", e1[i].u, e1[i].v, dis[e1[i].v] - dis[e1[i].u]); } else printf("%d %d %d\n", e1[i].u, e1[i].v, 9); } return 0; } ```