fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. struct edge {
  7. 	size_t finish;
  8. 	int weight;
  9. 	edge(size_t finish, int weight);
  10. 	bool operator!=(const edge& other) {
  11. 		return (finish != other.finish);
  12. 	}
  13. };
  14.  
  15. edge::edge(size_t fin, int weig)
  16. 	: finish(fin), weight(weig)
  17. {
  18. 	//std::cout<<this->finish<< weight<<"jjj";
  19. }
  20.  
  21. const static size_t kmax_size = 1000 * 1000 * 1000;
  22.  
  23. enum VertexStatus {
  24. 	kundiscovered, kdiscovering, kprocecced
  25. };
  26.  
  27. bool BFS(const std::vector<std::vector<edge>>& graph, std::vector<size_t>& ansestors, std::vector<size_t>& distance, std::vector<bool>& is_used, size_t start) {
  28. 	std::queue<int> graph_queue;
  29. 	graph_queue.push(start);
  30. 	while (!graph_queue.empty()) {
  31. 		size_t current_node = graph_queue.front();
  32. 		is_used[current_node] = true;
  33. 		graph_queue.pop();
  34. 		for (auto iter : graph[current_node]) {
  35. 			if (is_used[iter.finish]) {
  36. 				if (distance[iter.finish] == distance[current_node]) {
  37. 					return false;
  38. 				}
  39. 			}
  40. 			if (!is_used[iter.finish]) {
  41. 				ansestors[iter.finish] = current_node;
  42. 				if (distance[iter.finish] == 5) {
  43. 					distance[iter.finish] = 1 - distance[current_node];
  44. 				}
  45. 				if (distance[iter.finish] == distance[current_node]) {
  46. 					return false;
  47. 				}
  48. 				is_used[iter.finish] = true;
  49. 				graph_queue.push(iter.finish);
  50. 			}
  51. 		}
  52. 	}
  53. 	return true;
  54. }
  55.  
  56.  
  57. bool IsTwoPart(const std::vector<std::vector<edge>>& graph) {
  58. 	std::vector<size_t> ansestors(graph.size(), kmax_size);
  59. 	std::vector<size_t> part(graph.size(), 5);
  60. 	std::vector<bool> is_used(graph.size(), false);
  61. 	part[0] = 0;
  62. 	for (size_t i = 0; i < graph.size(); ++i) {
  63. 		if (!is_used[i]) {
  64. 			part[i] = 0;
  65. 			if (!BFS(graph, ansestors, part, is_used, i)) {
  66. 				return false;
  67. 			}
  68. 		}
  69. 	}
  70. 	return true;
  71. }
  72.  
  73. std::vector<size_t> DFS(const std::vector<std::vector<edge>>& graph, std::vector<VertexStatus>& nodes_colors, size_t start, size_t& result_e, std::vector<edge>& ansestors, std::vector<size_t>& cycle_vertecies, size_t ans, std::vector<int>& result, size_t& beg, int& shift, std::vector<edge>& path) {
  74. 	nodes_colors[start] = kdiscovering;
  75. 	//std::vector<size_t> path;
  76. 	//std::cout<<start<<nodes_colors[start]<<graph[1][0] << nodes_colors[graph[1][0]] << "\n";
  77. 	//std::cout << start << nodes_colors[start] << "\n";
  78. 	for (auto vert : graph[start]) {
  79. 		//std::cout << start << vert.finish << vert.weight<< "mmmm"<<"\n";
  80. 		//for (auto it : ansestors) {
  81. 		//	std::cout << it << " ";
  82. 		//}
  83. 	//	std::cout << "\n";
  84.  
  85. 		if (nodes_colors[vert.finish] == kdiscovering && vert.finish != ans) {
  86. 			//std::cout << vert.finish << start << vert.weight << "vertstart" << "\n";// << " " << ansestors[start].finish << ansestors[ansestors[start].finish].finish << "\n";//<< ansestors[ansestors[ansestors[start]]]<< "ppp" << "\n";
  87. 			if (path.size() == 0) {
  88. 				auto iter = edge(start, vert.weight);
  89. 				iter.finish = start;
  90. 				int last_node;
  91. 				iter.weight = 0;
  92. 				for (; iter != vert; iter = ansestors[iter.finish]) {
  93. 					//return 0;
  94.  
  95. 					//std::cout << iter.finish <<" "<< iter.weight<< " "<<ansestors[iter.finish].finish << "ffff"<< "\n";
  96. 					path.push_back(iter);
  97. 					if (iter.finish != vert.finish) {
  98. 						last_node = iter.finish;
  99. 					}
  100. 				}
  101. 				//	return 0; 
  102. 				int tmp;
  103. 				//std::cout<<last_node<<vert.finish<<"qqqqqq";
  104. 				for (auto it : graph[last_node]) {
  105. 					if (it.finish == vert.finish) {
  106. 						tmp = it.weight;
  107. 					}
  108. 				}
  109. 				vert.weight = tmp;
  110. 				//std::cout<<vert.finish<<vert.weight<<start<<"\n";
  111. 				path.push_back(vert);
  112. 				//std::cout << "path_size" << path.size();
  113.  
  114. 				if (path.size() % 2 == 1) {
  115. 					//std::cout << "yyyy" << "\n";
  116. 					for (auto l : path) {
  117. 						//std::cout << l.finish << l.weight<< " ";
  118. 					}
  119. 					//std::cout<< "hhhh"<< start<<"\n";
  120. 					result[start] = 0;
  121. 					beg = start;
  122. 					//std::cout<< beg<<"mmuuumm";
  123. 					//std::cout << start << path.size() << " iiiiiii" << "\n";
  124. 					int temp;
  125. 					for (auto iter : graph[start]) {
  126. 						if (iter.finish == path[path.size() - 1].finish) {
  127. 							temp = iter.weight;
  128. 						}
  129. 					}
  130. 					//std::cout<<temp<<"wwww";
  131. 					for (int i = 1;i < path.size();++i) {
  132. 						result[path[i].finish] = path[i].weight - result[path[i - 1].finish] - 2;
  133. 						//std::cout << path[i - 1].finish << path[i].finish << result[path[i].finish] << result[path[i - 1].finish] << path[i].weight  << "uuuu"<<"\n";
  134. 					}
  135. 					//std::cout << path[2].finish<<path[2].weight<< "kkkk;";
  136. 						//for (auto l :result) {
  137. 					///		std::cout << l + 1 << " ";
  138. 					//	}
  139. 						//std::cout << "\n";
  140. 					shift = temp - 2 - result[start] - result[path[path.size() - 1].finish];
  141. 					//std::cout <<start << shift <<"llll";
  142. 					//std::cout << shift << start << result[start] << "aaaaa" << "\n";
  143. 					ansestors[vert.finish] = edge(start, 0);
  144. 					return {};
  145. 					//result_e = vert;
  146. 					//cycle_vertecies.push_back(vert);
  147. 					//std::cout<< vert<<"vvvv";
  148. 					return {};
  149. 				}
  150. 			}
  151. 			if (path.size() % 2 == 0) {
  152. 				path.clear();
  153. 			}
  154. 		}
  155. 		if (nodes_colors[vert.finish] == kundiscovered) {
  156. 			//std::cout << start << " " << vert.finish << vert.weight<< "\n";
  157. 			ansestors[vert.finish] = edge(start, vert.weight);
  158. 			ansestors[vert.finish].weight = vert.weight;
  159. 			//std::cout << vert << nodes_colors[vert] << "\n";
  160. 			DFS(graph, nodes_colors, vert.finish, result_e, ansestors, cycle_vertecies, start, result, beg, shift, path);
  161. 			//return res;
  162. 		}
  163.  
  164. 	}
  165. 	nodes_colors[start] = kprocecced;
  166. 	//cycle_vertecies.clear();
  167. 	//for (auto it :ansestors) {
  168. //		std::cout << it << " ";
  169. ////	}
  170. ///	std::cout << "hhhh" << "\n";
  171. 	return {};
  172. }
  173.  
  174. void GetOddCycle(const std::vector<std::vector<edge>>& graph, std::vector<int>& result, size_t& start, int& shift) {
  175. 	//std::vector<size_t> result;
  176. 	std::vector<edge> path;
  177. 	std::vector<size_t> cycle_vertecies;
  178. 	std::vector<VertexStatus> nodes_colors(graph.size(), kundiscovered);
  179. 	std::vector<edge> ansestors(graph.size(), edge(kmax_size, kmax_size));
  180. 	std::vector<bool> is_used(graph.size(), false);
  181. 	size_t result_e = kmax_size;
  182. 	//for (size_t i = 0; i < graph.size(); ++i) {
  183. 	//	if (nodes_colors[i] == kundiscovered) {
  184. 			//std::cout<< "uuuuu";
  185. 	auto res = DFS(graph, nodes_colors, 0, result_e, ansestors, cycle_vertecies, kmax_size, result, start, shift, path);
  186. 	//std::cout << start<< shift<< "rrrr";
  187. 	return;
  188.  
  189. 	//	}
  190. 	//}
  191. 	/*//std::cout<<result_e<<"uuuuu";
  192. 	//size_t start;
  193. 	if (result_e == kmax_size) {
  194. 		return {};
  195. 	}
  196. 	std::vector<size_t> path_from_start_to_finish;
  197. 	//for (auto it : ansestors) {
  198. 		//std::cout<< it << " ";
  199. //	}
  200. //	std::cout << "\n";
  201. 	for (auto res_e : cycle_vertecies) {
  202. 		//std::cout << res_e << "\n";
  203. 		for (auto iter = ansestors[res_e]; iter != res_e; iter = ansestors[iter]) {
  204. 			path_from_start_to_finish.push_back(iter);
  205. 		}
  206. 		//std::cout<< path_from_start_to_finish.size() << "\n";
  207. 		//for (auto it : path_from_start_to_finish) {
  208. 	//		std::cout << it << " ";
  209. 	//	}
  210. 		return path_from_start_to_finish;
  211. 		if (path_from_start_to_finish.size() % 2 == 0) {
  212. 			path_from_start_to_finish.push_back(result_e);
  213. 			std::reverse(path_from_start_to_finish.begin(), path_from_start_to_finish.end());
  214. 			for (auto vert : path_from_start_to_finish) {
  215. 				result.push_back(vert);
  216. 			}
  217. 			return {};
  218. 		}
  219. 		else {
  220. 			path_from_start_to_finish.clear();
  221. 		}
  222. 	}
  223. 	*/
  224. 	//return;
  225. }
  226.  
  227. void BFSOdd(const std::vector<std::vector<edge>>& graph, std::queue<int>& graph_queue, std::vector<bool>& is_used, size_t start, std::vector<int>& result, int& shift) {
  228. 	//graph_queue.push(start);
  229. 	//std::queue<int> ans_q;
  230. 	//int shift;
  231. 	//ans_q.push(kmax_size);
  232. 	/*	while (!graph_queue.empty()) {
  233. 			size_t top = graph_queue.front();
  234. 			int ans = ans_q.front();
  235. 			ans_q.pop();
  236. 			is_used[top] = true;
  237. 			graph_queue.pop();
  238. 			for (auto iter : graph[top]) {
  239. 				if (!is_used[iter] && iter!=ans) {
  240. 					result[iter] = edge_numbers[top][iter] - result[top];
  241. 					ansestors[iter] = top;
  242. 					distance[iter] = distance[top] + 1;
  243. 					is_used[iter] = true;
  244. 					graph_queue.push(iter);
  245. 					ans_q.push(top);
  246. 					std::cout << iter << result[iter] << "\n";
  247. 				}
  248. 				if (is_used[iter]) {
  249.  
  250. 					shift = edge_numbers[top][iter] - result[iter] - result[top];
  251. 					std::cout<< top<< " " <<iter<<shift<<"\n";
  252. 					break;
  253. 					//for (int i = 0;i < result.size();++i) {
  254. 					//	result[i] = result[i] + (shift / 2);
  255. 					//	std::cout<<result[i];
  256. 				//	}
  257. 				//	std::cout<<"\n";
  258. 				}
  259. 			}
  260. 		}
  261. 		for (int i=0;i<is_used.size();++i) {
  262. 			is_used[i]=false;
  263. 		}*/
  264. 		//std::cout<<shift<<start<<"gggg";
  265. 	graph_queue.push(start);
  266. 	result[start] += (shift / 2);
  267. 	//std::cout<<start << shift << result[start] << "zzzzz";
  268. 	for (auto k : result) {
  269. 		//std::cout << k << " ";
  270. 	}
  271. 	//std::cout << "\n" << start << shift << "\n";
  272. 	//std::cout <<"nnnn";
  273. 	//std::cout << shift;
  274. 	while (!graph_queue.empty()) {
  275. 		size_t top = graph_queue.front();
  276. 		//int ans = ans_q.front();
  277. 		//ans_q.pop();
  278. 		is_used[top] = true;
  279. 		graph_queue.pop();
  280. 		for (auto iter : graph[top]) {
  281. 			if (!is_used[iter.finish]) {
  282. 				result[iter.finish] = iter.weight - 2 - result[top];
  283. 				//ansestors[iter] = top;
  284. 				//distance[iter] = distance[top] + 1;
  285. 				is_used[iter.finish] = true;
  286. 				graph_queue.push(iter.finish);
  287. 				//ans_q.push(top);
  288. 				//std::cout << top << iter << result[iter] << "tttt"<< "\n";
  289. 			}
  290. 		}
  291. 	}
  292. 	for (auto l : result) {
  293. 		std::cout << l + 1 << " ";
  294. 	}
  295. 	//std::cout<< "sssss"<<"\n";
  296. }
  297.  
  298. std::vector<int> GetPath(const std::vector<std::vector<edge>>& graph) {
  299. 	const size_t max_size = 1000 * 1000 * 1000;
  300. 	int shift;
  301. 	size_t start;
  302. 	size_t gr_size = graph.size();
  303. 	std::vector<int> result(gr_size, kmax_size);
  304. 	std::queue<int> graph_queue;
  305. 	GetOddCycle(graph, result, start, shift);
  306. 	//std::cout<<start<<shift<<"\n";
  307. 	//std::cout<< shift<<"bbbbb"<<"\n";
  308. 	std::vector<size_t> ansestors(graph.size(), max_size);
  309. 	//std::vector<size_t> distance(graph.size(), max_size);
  310. 	std::vector<bool> is_used(graph.size(), false);
  311. 	//distance[start] = 0;
  312. 	//for (int vert = 0;vert < graph.size();++vert) {
  313. 	///	if (!is_used[vert]) {
  314. 		//	result[vert] = 0;
  315. 			//distance[vert] = 0;
  316. 	BFSOdd(graph, graph_queue, is_used, start, result, shift);
  317. 	//	}
  318. 	//}
  319.  
  320. 	/*if (is_used[finish]) {
  321. 		//std::cout << distance[finish] << "\n";
  322. 		std::vector<size_t> path_from_start_to_finish;
  323. 		for (auto iter = finish; iter != start; iter = ansestors[iter]) {
  324. 			path_from_start_to_finish.push_back(iter);
  325. 		}
  326. 		path_from_start_to_finish.push_back(start);
  327. 		std::reverse(path_from_start_to_finish.begin(), path_from_start_to_finish.end());
  328. 		for (auto iter = path_from_start_to_finish.begin(); iter != path_from_start_to_finish.end(); ++iter) {
  329. 			result.push_back(*iter + 1);
  330. 		}
  331. 	}*/
  332. 	return result;
  333. }
  334.  
  335. std::vector<int> Even(const std::vector<std::vector<edge>>& graph) {
  336. 	bool flag = true;
  337. 	std::vector<int> result(graph.size(), kmax_size);
  338. 	for (size_t i = 0;i < graph.size();++i) {
  339. 		std::queue<int> graph_queue;
  340.  
  341. 		//std::vector<size_t> ansestors(graph.size(), kmax_size);
  342. 		//std::vector<size_t> part(graph.size(), 5);
  343. 		std::vector<bool> is_used(graph.size(), false);
  344. 		graph_queue.push(i);
  345. 		result[i] = 0;
  346. 		while (!graph_queue.empty()) {
  347. 			size_t current_node = graph_queue.front();
  348. 			is_used[current_node] = true;
  349. 			graph_queue.pop();
  350. 			for (auto iter : graph[current_node]) {
  351. 				if (is_used[iter.finish]) {
  352. 					//std::cout << iter << current_node << result[iter] << result[current_node] << edge_numbers[current_node][iter] - 2 << "\n";
  353. 					//if (distance[iter] == distance[current_node]) {
  354. 					//	return false;
  355. 					//}
  356. 				}
  357. 				if (!is_used[iter.finish]) {
  358. 					result[iter.finish] = iter.weight - 2 - result[current_node];
  359. 					if (result[iter.finish] < 0) {
  360. 						result.clear();
  361. 						result.resize(graph.size());
  362. 						flag = false;
  363. 						continue;
  364. 					}
  365. 					graph_queue.push(iter.finish);
  366. 				}
  367. 			}
  368. 		}
  369. 		if (flag) {
  370. 			break;
  371. 		}
  372. 	}
  373. 	/*	for (auto it : result) {
  374. 				std::cout<<it<< " ";
  375. 		}
  376. 		std::cout<< "\n"; 
  377. 	int max_val = kmax_size;
  378. 	int index = 0;
  379. 	for (int i = 0;i < result.size();++i) {
  380. 		if (result[i] < max_val) {
  381. 			max_val = result[i];
  382. 			index = i;
  383. 		}
  384. 	}
  385. 	//std::cout<<index<<max_val <<"\n";
  386. 	std::queue<int> new_graph_queue;
  387. 	std::queue<int> graph_queue_t;
  388. 	for (int i = 0;i < is_used.size();++i) {
  389. 		is_used[i] = false;
  390. 	}
  391. 	for (int i = 0;i < result.size();++i) {
  392. 		result[i] = kmax_size;
  393. 	}
  394. 	//graph_queue.clear();
  395. 	graph_queue_t.push(1);
  396. 	result[1] = 0;
  397. 	while (!graph_queue_t.empty()) {
  398. 		size_t current_node = graph_queue_t.front();
  399. 		is_used[current_node] = true;
  400. 		graph_queue_t.pop();
  401. 		for (auto iter : graph[current_node]) {
  402. 			if (is_used[iter.finish]) {
  403. 				//std::cout << iter << current_node << result[iter] << result[current_node] << edge_numbers[current_node][iter] - 2 << "\n";
  404. 				//if (distance[iter] == distance[current_node]) {
  405. 				//	return false;
  406. 				//}
  407. 			}
  408. 			if (!is_used[iter.finish]) {
  409. 				result[iter.finish] = iter.weight - 2 - result[current_node];
  410. 				graph_queue_t.push(iter.finish);
  411. 			}
  412. 		}
  413. 	}
  414. 	/*	for (auto it : result) {
  415. 				std::cout<<it<< " ";
  416. 		}
  417. 		std::cout<< "yyy" << "\n";
  418. 	int max_val_s = kmax_size;
  419. 	int index_s = 0;
  420. 	for (int i = 0;i < result.size();++i) {
  421. 		if (result[i] < max_val_s) {
  422. 			max_val_s = result[i];
  423. 			index_s = i;
  424. 		}
  425. 	}
  426. 	//std::cout<< max_val_s<<index_s<<"\n";
  427. 	std::vector<int> new_result(graph.size(), kmax_size);
  428. 	std::vector<bool> new_is_used(graph.size(), false);
  429.  
  430. 	if (max_val_s <= max_val) {
  431. 		new_result[index_s] = 0;
  432. 		new_graph_queue.push(index_s);
  433. 	}
  434. 	else {
  435. 		new_result[index] = 0;
  436. 		new_graph_queue.push(index);
  437. 	}
  438. 	while (!new_graph_queue.empty()) {
  439. 		size_t new_current_node = new_graph_queue.front();
  440. 		new_is_used[new_current_node] = true;
  441. 		new_graph_queue.pop();
  442. 		for (auto new_iter : graph[new_current_node]) {
  443. 			if (new_is_used[new_iter.finish]) {
  444. 				//std::cout << iter << current_node << result[iter] << result[current_node] << edge_numbers[current_node][iter] - 2 << "\n";
  445. 				//if (distance[iter] == distance[current_node]) {
  446. 				//	return false;
  447. 				//}
  448. 			}
  449. 			if (!new_is_used[new_iter.finish]) {
  450. 				new_result[new_iter.finish] = new_iter.weight - 2 - new_result[new_current_node];
  451. 				new_graph_queue.push(new_iter.finish);
  452. 			}
  453. 		}
  454. 	}
  455. 	//std::cout<<index << "\n";*/
  456. 	for (auto r : result) {
  457. 		std::cout << r + 1 << " ";
  458. 	}
  459. 	return result;
  460. }
  461.  
  462. int main() {
  463. 	size_t node_q, temp, tmp;
  464. 	int val;
  465. 	size_t edge_q, start, finish;
  466. 	std::cin >> node_q >> edge_q;
  467. 	//std::vector<std::vector<size_t>> edge_numbers(node_q, std::vector<size_t>(node_q, 0));
  468. 	std::vector<std::vector<edge>> graph(node_q);
  469. 	for (int i = 0; i < edge_q; ++i) {
  470. 		std::cin >> temp >> tmp >> val;
  471. 		//std::cout<<"\n"<<val << "\n";
  472. 		edge tede = edge(tmp - 1, val);
  473. 		tede.weight = val;
  474. 		//std::cout<<"kkkk"<<val<<" "<<tede.weight<<"\n";
  475. 		graph[temp - 1].push_back(tede);
  476. 		//std::cout<<"bbbb"<<tede.weight<<"\n";
  477. 		edge tedge = edge(temp - 1, val);
  478. 		tedge.weight = val;
  479. 		graph[tmp - 1].push_back(tedge);
  480. 		//edge_numbers[temp - 1][tmp - 1] = val;
  481. 		//edge_numbers[tmp - 1][temp - 1] = val;
  482. 	}
  483. 	//std::cout << graph[0][0] << graph[0][1];
  484. 	//std::cout << "jjjj";
  485. 	std::vector<int> result(node_q, kmax_size);
  486. 	if (IsTwoPart(graph)) {
  487. 		//std::cout<< "pppp";
  488. 		Even(graph);
  489. 	}
  490. 	else {
  491. 		auto res = GetPath(graph);
  492. 	}
  493. 	/*if (res.size() == 0) {
  494. 		std::cout << "NO";
  495. 	}
  496. 	else {
  497. 		std::cout<<"YES" <<"\n";
  498. 		std::vector<int> str = GetPath(graph, edge_numbers);
  499. 		for (auto iter : str) {
  500. 			std::cout << iter << " ";
  501. 		}
  502. 	}*/
  503.  
  504. 	return 0;
  505. }
Success #stdin #stdout 0s 4428KB
comments (?)
stdin
copy 
4 3
1 2 3
2 3 5
3 4 7
stdout
copy 
1 2 3 4
https://ideone.com/ppIS86
language:
C++14 (gcc 8.3)
created:
3 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!