自动搬运

查看原文

来自洛谷，原作者为

	Rbu_nas nya nya nya

搬运于2025-08-24 22:12:17，当前版本为作者最后更新于2019-10-14 10:32:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意简述：

给定一些有向边，对她们赋上边权 $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]$。仔细想想这不就可以建差分约束系统求解了吗？

---

简单介绍一下差分约束，单源最短路中我们有：

$$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:}$

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;
}

为了能让大家有自己的思考与理解，题解代码中没有注释。详细注释版本的放在剪贴板中。

另：博主是个菜鸡，如果哪里有误麻烦指出orz