题解P5590 赛车游戏

Rbu_nas

2019-10-14 10:32:30

Solution

题意简述: 给定一些有向边,对她们赋上边权 $w\in[1,9]$,使得每条 $1\to n$ 的简单路径长相等。 --- 不得不说这题相当有趣,, 比赛的时候写的是钦定每条在 $1\to n$ 路径上边权为 $1$,统计路径总数以及每条路径的长度和,然后求出公共 gcd 和 lcm,通分后再进行一遍约分。但是很遗憾的是,在钦定边权为 $1$ 时就可能出现 out of range of [1,9] 的情况。每条边的边权无法确认,于是我们只能从题目本身入手 然后就可以发现,,,由于给定的边权 $w\in[1,9]$,又有 $dis_u + w(u,v) = dis_v$,说明 $dis_v - dis_u\in[1,9]$。仔细想想这不就可以建差分约束系统求解了吗? ![](https://ftp.bmp.ovh/imgs/2019/10/d868f9f03e00d068.png) --- 简单介绍一下[差分约束](https://oi-wiki.org/graph/diff-constraints/),单源最短路中我们有: $$dis_{to}\le dis_u + w(u,to)$$ 故有: $$dis_{to} - dis_u\le w(u, to)$$ 也就是说,如果给定 $x + y \ge z$,就可以转化成 $z - y\le x$,然后 `add(y, z, x)` $y\to z$ 建边。 在这道题中我们有 $a\to b$ 的边,同时有: $$1\le dis_b - dis_a \color{orange}\Rightarrow \color{c}dis_a - dis_b \le -1$$ $$dis_b - dis_a\le 9$$ 所以建边:`add(b, a, -1), add(a, b, 9)` 最后 SPFA 判断差分约束系统是否有解(是否有负环),没了。 没了?没了。 当然还有一些注意事项: + 题目给的是有向边,要判断是否能从 $1\to n$ + 不在 $1\to n$ 路径上的边的边权可以随便标,不会对答案产生影响,所以我们先标记出 $1\to n$ 路上的点,然后再建边。对那些“无用”边建边会让我们得到错误的约束。 --- $\texttt{Code:}$ ```cpp const int MAXN = 1e3 + 3; const int MAXM = 2e3 + 3; const int LEN = 1 << 11; inline int read() { int x = 0; bool f = 1; register char c = getchar(); for(; !std::isdigit(c); c = getchar()) f ^= c == '-'; for(; std::isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); return f ? x : -x; } int n, m, u[MAXM], v[MAXM], dis[MAXN], times[MAXN]; bool inq[MAXN], vis1[MAXN], visn[MAXN]; int fa[MAXN]; inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } inline void merge(int x, int y) { int a = find(x), b = find(y); if(a == b) return ; fa[a] = b; } struct Edges { int to, dis, nxt; Edges() {} Edges(int to, int dis, int nxt): to(to), dis(dis), nxt(nxt) {} } edge[MAXM << 1]; int head[MAXN]; inline void addEdge(int u, int v, int d) { static int cnt = 0; edge[++cnt] = Edges(v, d, head[u]); head[u] = cnt; } std::vector<int> G[MAXN], nG[MAXN]; inline void addEdge(int u, int v, std::vector<int> ver[]) { ver[u].push_back(v); } void dfs(int x) { int size = G[x].size(); for(int i = 0; i < size; ++i) { int to = G[x][i]; if(vis1[to]) continue; vis1[to] = 1; dfs(to); } } void nDfs(int x) { int size = nG[x].size(); for(int i = 0; i < size; ++i) { int to = nG[x][i]; if(visn[to]) continue; visn[to] = 1; nDfs(to); } } struct Queue { int l, r, q[LEN + 10]; Queue(): l(1), r(0) {} inline void push(int x) { q[++r & (LEN - 1)] = x; } inline void pop() { ++l; } inline int front() { return q[l & (LEN - 1)]; } inline bool empty() { return l > r; } }; inline bool SPFA(int s) { std::memset(dis, 0x3f, sizeof dis); dis[s] = 0; inq[s] = 1; times[s] = 1; Queue q; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].to; if(dis[u] + edge[i].dis < dis[v]) { dis[v] = dis[u] + edge[i].dis; if(++times[v] > n) return 0; if(!inq[v]) q.push(v), inq[v] = 1; } } } return 1; } signed main() { n = read(), m = read(); for(int i = 1; i <= n; ++i) fa[i] = i; for(int i = 1; i <= m; ++i) { u[i] = read(), v[i] = read(); addEdge(u[i], v[i], G), addEdge(v[i], u[i], nG); merge(u[i], v[i]); } if(find(1) != find(n)) { puts("-1"); return 0; } dfs(1); nDfs(n); static bool flag[MAXN] = {0}; for(int i = 1; i <= n; ++i) if(vis1[i] && visn[i]) flag[i] = 1; if(!vis1[n]) { puts("-1"); return 0; } flag[1] = flag[n] = 1; for(int i = 1; i <= m; ++i) if(flag[u[i]] && flag[v[i]]) addEdge(u[i], v[i], 9), addEdge(v[i], u[i], -1); if(!SPFA(1)) { puts("-1"); return 0; } printf("%d %d\n", n, m); for(int i = 1; i <= m; ++i) { printf("%d %d ", u[i], v[i]); if(flag[u[i]] && flag[v[i]]) printf("%d\n", dis[v[i]] - dis[u[i]]); else puts("1"); } return 0; } ``` 为了能让大家有自己的思考与理解,题解代码中没有注释。详细注释版本的放在[剪贴板](http://ideone.com/mIcphC)中。 另:博主是个菜鸡,如果哪里有误麻烦指出orz