fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. const int MAXN = 1e3 + 3;
  4. const int MAXM = 2e3 + 3;
  5. const int LEN = 1 << 11;
  6.  
  7. inline int read() {
  8. 	int x = 0; bool f = 1; register char c = getchar();
  9. 	for(; !std::isdigit(c); c = getchar()) f ^= c == '-';
  10. 	for(; std::isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  11. 	return f ? x : -x;
  12. }
  13.  
  14. int n, m, u[MAXM], v[MAXM], dis[MAXN], times[MAXN]; 
  15. bool inq[MAXN], vis1[MAXN], visn[MAXN];
  16.  
  17. int fa[MAXN];
  18.  
  19. inline int find(int x) {
  20. 	return fa[x] == x ? x : fa[x] = find(fa[x]);
  21. }
  22. inline void merge(int x, int y) {
  23. 	int a = find(x), b = find(y);
  24. 	if(a == b) return ;
  25. 	fa[a] = b;
  26. }
  27.  
  28. struct Edges {
  29. 	int to, dis, nxt;
  30. 	Edges() {}
  31. 	Edges(int to, int dis, int nxt): to(to), dis(dis), nxt(nxt) {}
  32. } edge[MAXM << 1];
  33.  
  34. int head[MAXN];
  35.  
  36. inline void addEdge(int u, int v, int d) {
  37. 	static int cnt = 0;
  38. 	edge[++cnt] = Edges(v, d, head[u]);
  39. 	head[u] = cnt;
  40. }
  41.  
  42. std::vector<int> G[MAXN], nG[MAXN];
  43. inline void addEdge(int u, int v, std::vector<int> ver[]) {
  44. 	ver[u].push_back(v);
  45. }
  46.  
  47. void dfs(int x) {
  48. 	int size = G[x].size();
  49. 	for(int i = 0; i < size; ++i) {
  50. 		int to = G[x][i];
  51. 		if(vis1[to]) continue;
  52.  
  53. 		vis1[to] = 1; dfs(to);
  54. 	}
  55. }
  56. void nDfs(int x) {
  57. 	int size = nG[x].size();
  58. 	for(int i = 0; i < size; ++i) {
  59. 		int to = nG[x][i];
  60. 		if(visn[to]) continue;
  61.  
  62. 		visn[to] = 1; nDfs(to);
  63. 	}
  64. }
  65.  
  66. struct Queue {
  67. 	int l, r, q[LEN + 10];
  68. 	Queue(): l(1), r(0) {}
  69.  
  70. 	inline void push(int x) { q[++r & (LEN - 1)] = x; }
  71. 	inline void pop() { ++l; }
  72. 	inline int front() { return q[l & (LEN - 1)]; }
  73. 	inline bool empty() { return l > r; }
  74. };
  75.  
  76. inline bool SPFA(int s) {
  77. 	std::memset(dis, 0x3f, sizeof dis);
  78. 	dis[s] = 0; inq[s] = 1; times[s] = 1;
  79. 	Queue q; q.push(s);
  80.  
  81. 	while(!q.empty()) {
  82. 		int u = q.front(); q.pop();
  83. 		inq[u] = 0;
  84. 		for(int i = head[u]; i; i = edge[i].nxt) {
  85. 			int v = edge[i].to;
  86. 			if(dis[u] + edge[i].dis < dis[v]) {
  87. 				dis[v] = dis[u] + edge[i].dis;
  88. 				if(++times[v] > n) return 0;
  89. 				if(!inq[v]) q.push(v), inq[v] = 1;
  90. 			}
  91. 		}
  92. 	}
  93. 	return 1;
  94. }
  95.  
  96. signed main() {
  97. 	n = read(), m = read();
  98.  
  99. 	for(int i = 1; i <= n; ++i) fa[i] = i;
  100.  
  101. 	for(int i = 1; i <= m; ++i) {
  102. 		u[i] = read(), v[i] = read();
  103. 		addEdge(u[i], v[i], G), addEdge(v[i], u[i], nG);
  104. 		merge(u[i], v[i]);
  105. 	}
  106.  
  107. 	/*
  108. 	并查集判断 1 和 n 是否联通（其实没啥用
  109. 	nG[] 存反边 ==> n -> 1
  110. 	G[] 存正向边 ==> 1 -> n
  111. 	*/
  112.  
  113. 	if(find(1) != find(n)) {
  114. 		puts("-1");
  115. 		return 0;
  116. 	}
  117.  
  118. 	dfs(1); nDfs(n);
  119.  
  120. 	static bool flag[MAXN] = {0};
  121. 	for(int i = 1; i <= n; ++i) if(vis1[i] && visn[i]) flag[i] = 1;
  122. 	if(!vis1[n]) {
  123. 		puts("-1");
  124. 		return 0;	
  125. 	}
  126. 	flag[1] = flag[n] = 1;
  127.  
  128. 	/*
  129. 	注意这里是判断 1 到 n 中每个点是否在答案路径上，枚举的是 1 ~ n
  130. 	vis1[] 是从 1 到 n 上经过的点
  131. 	visn[] 是从 n 到 1 上经过的点
  132. 	因为是有向边，所以要判断一下 1 可不可以到 n
  133.  
  134. 	比如:
  135. 	3 2
  136. 	3 1
  137. 	1 2
  138.  
  139. 	ans: -1
  140. 	*/
  141.  
  142. 	for(int i = 1; i <= m; ++i)
  143. 		if(flag[u[i]] && flag[v[i]]) addEdge(u[i], v[i], 9), addEdge(v[i], u[i], -1);
  144.  
  145. 	if(!SPFA(1)) {
  146. 		puts("-1");
  147. 		return 0;
  148. 	}
  149.  
  150. 	/*
  151. 	只对答案路径上的点建边，跑差分约束
  152. 	如果出现负环，差分约束系统无解。
  153. 	*/
  154.  
  155. 	printf("%d %d\n", n, m);
  156. 	for(int i = 1; i <= m; ++i) {
  157. 		printf("%d %d ", u[i], v[i]);
  158. 		if(flag[u[i]] && flag[v[i]]) printf("%d\n", dis[v[i]] - dis[u[i]]);
  159. 		else puts("1"); //随便输出啥，反正无用边不影响
  160. 	}
  161. 	return 0;
  162. }
  163.  
Success #stdin #stdout 0s 4300KB
comments (?)
stdin
copy 
10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
stdout
copy 
10 10
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
1 10 9
https://ideone.com/mIcphC
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!