AlgorithmStudy/2014/virtual - Revision history

Maintenance script: Repair batch-0008 pages from live compare

2026-03-27T01:40:36Z

Repair batch-0008 pages from live compare

← Older revision		Revision as of 01:40, 27 March 2026
Line 19:		Line 19:
	* [http://183.106.113.109/displaysrc.php?id=1178830]		* [http://183.106.113.109/displaysrc.php?id=1178830]
	points = int(raw_input())		points = int(raw_input())
	point_current, point_end = [int(i) for i in raw_input().split()]		point_current, point_end = [int(i) for i in raw_input().split()]

	graph = [[-1] * (points + 1) for i in range(points + 1)]		graph = [[-1] * (points + 1) for i in range(points + 1)]
	point_in = [0] * (points + 1)		point_in = [0] * (points + 1)
	point_parent = [0] * (points + 1)		point_parent = [0] * (points + 1)
	point_parent[point_current] = -1		point_parent[point_current] = -1
	point_flow = [0] * (points + 1)		point_flow = [0] * (points + 1)
	point_flow[point_current] = 99999		point_flow[point_current] = 99999

	while True:		while True:
	try:		try:
	input_data = [int(i) for i in raw_input().split()]		input_data = [int(i) for i in raw_input().split()]
	if not input_data:		if not input_data:
	break		break
	graph[input_data[0~~]][~~input_data[1]] = input_data[2]		graph[input_data[0]][input_data[1]] = input_data[2]
	point_in[input_data[1]] += 1		point_in[input_data[1]] += 1
	except EOFError:		except EOFError:
	break		break

	stack = [point_current]		stack = [point_current]
	for i in range(1, points + 1):		for i in range(1, points + 1):
	if point_in[i] == 0 and i != point_current:		if point_in[i] == 0 and i != point_current:
	stack.append(i)		stack.append(i)

Line 46:		Line 46:
	point_current = stack.pop()		point_current = stack.pop()
	for i in range(points + 1):		for i in range(points + 1):
	flow = min(graph[point_current][i], point_flow[point_current])		flow = min(graph[point_current][i], point_flow[point_current])
	if flow != -1:		if flow != -1:
	graph[point_current][i] = -1		graph[point_current][i] = -1
	if flow > point_flow[i]:		if flow > point_flow[i]:
	point_flow[i] = flow		point_flow[i] = flow
	point_parent[i] = point_current		point_parent[i] = point_current
	point_in[i] -= 1		point_in[i] -= 1
	if point_in[i] == 0:		if point_in[i] == 0:
	stack.append(i)		stack.append(i)

	print point_flow[point_end]		print point_flow[point_end]

	path = []		path = []
	point_current = point_end		point_current = point_end
	while point_current != -1:		while point_current != -1:
	path.append(point_current)		path.append(point_current)
	point_current = point_parent[point_current]		point_current = point_parent[point_current]

	path.reverse()		path.reverse()
Line 112:		Line 112:
	int start, end1, answer = 0, answerCount = 9999999;		int start, end1, answer = 0, answerCount = 9999999;
	int startClock, endClock;		int startClock, endClock;
	int adjMatrix[size][size];		int adjMatrix[size][size];
	int checkNode[size];		int checkNode[size];
	vector < list <Node> > adjList;		vector < list <Node> > adjList;
	queue < int > processQ;		queue < int > processQ;
Line 119:		Line 119:
	void dfs(int currentPos, int minCost, int count){		void dfs(int currentPos, int minCost, int count){
	currentPath.push(currentPos);		currentPath.push(currentPos);
	checkNode[currentPos] = VISITED;		checkNode[currentPos] = VISITED;

	if(currentPos == start){		if(currentPos == start){
Line 136:		Line 136:
	}		}

	for(list<Node>::iterator it1 = adjList[currentPos].begin(); it1 != adjList[currentPos].end(); it1++){		for(list<Node>::iterator it1 = adjList[currentPos].begin(); it1 != adjList[currentPos].end(); it1++){
	int nextNode = (*it1).destination;		int nextNode = (*it1).destination;
	int cost = (*it1).cost;		int cost = (*it1).cost;
	if(checkNode[nextNode] != VISITED && answer <= cost){		if(checkNode[nextNode] != VISITED && answer <= cost){
	dfs(nextNode, min(minCost, cost), count + 1);		dfs(nextNode, min(minCost, cost), count + 1);
	checkNode[nextNode] = UNVISTED;		checkNode[nextNode] = UNVISTED;
	currentPath.pop();		currentPath.pop();
	}		}
Line 158:		Line 158:
	while(!cin.eof()){		while(!cin.eof()){
	cin>>s>>e>>cost;		cin>>s>>e>>cost;
	adjMatrix[e][s] = cost;		adjMatrix[e][s] = cost;
	adjList[e].push_back(Node(s, cost));		adjList[e].push_back(Node(s, cost));
	}		}
	for(int i = 1; i<=n; i++){		for(int i = 1; i<=n; i++){
	adjList[i].sort(compare_Node);		adjList[i].sort(compare_Node);
	}		}
	dfs(end1, 999999999, 0);		dfs(end1, 999999999, 0);
Line 173:		Line 173:
	return 0;		return 0;
	}		}

imported>trailblaze at 01:36, 18 February 2014

2014-02-18T01:36:53Z

← Older revision		Revision as of 01:36, 18 February 2014
Line 76:		Line 76:
	* Stack에 담을 거니까 그냥 DP에서 SP까지 가는 경로를 찾자.		* Stack에 담을 거니까 그냥 DP에서 SP까지 가는 경로를 찾자.

	* 가지 치기 방법 : 내가 지금까지 구한 answer보다, 다른 ~~노드로~~ 연결 되는 간선의 비용이 작으면 탐색 할 필요가 없음.		* 가지 치기 방법 : 내가 지금까지 구한 answer보다, 다른 정점으로 연결 되는 간선의 비용이 작으면 탐색 할 필요가 없음.
	=== 겪었던 문제 ===		=== 겪었던 문제 ===
	* 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.		* 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.

imported>trailblaze at 01:36, 18 February 2014

2014-02-18T01:36:35Z

← Older revision		Revision as of 01:36, 18 February 2014
Line 84:		Line 84:
	* 첫 번째 해결방법 : 0.9초에 끊어서, 그 때까지 얻은 가장 좋은 값을 출력하게 해보자.		* 첫 번째 해결방법 : 0.9초에 끊어서, 그 때까지 얻은 가장 좋은 값을 출력하게 해보자.
	** 좋은 값을 주지 못함. 0.9초에 끊는 방법은 그만두기로 함.		** 좋은 값을 주지 못함. 0.9초에 끊는 방법은 그만두기로 함.
	* 두 번째 해결방법 : 다음 ~~노드로~~ 가는데 ~~Cost가~~ 높은 ~~edge부터~~ 탐색하자. adjList를 정렬함.		* 두 번째 해결방법 : 다음 정점으로 가는데 비용이 높은 간선부터 탐색하자. adjList를 정렬함.
	** 여전히 시간 초과		** 여전히 시간 초과
	* 세 번째 해결방법 : ~~소스를~~ 보던 중, 의도했던 가지 치기 코드가 잘못되었음을 발견.		* 세 번째 해결방법 : 코드를 보던 중, 의도했던 가지 치기 코드가 잘못되었음을 발견.
	** 가지 치기가 정상적으로 동작하니까, 잘 나옴. 첫 번째나 두 번째 시도가 별로 의미 없었음을 깨달음.		** 가지 치기가 정상적으로 동작하니까, 잘 나옴. 첫 번째나 두 번째 시도가 별로 의미 없었음을 깨달음.
	=== 코드 ===		=== 코드 ===

imported>trailblaze at 01:36, 18 February 2014

2014-02-18T01:36:04Z

← Older revision		Revision as of 01:36, 18 February 2014
Line 72:		Line 72:
	* Network Flow 문제로 나와있는데, 그냥 적절한 가지치기를 통해서 dfs로 경로를 탐색해나가도 될 것 같음. n도 100밖에 안되고, 인접행렬 대신에 인접리스트를 사용해서 적당하게 탐색 공간을 줄이면 시간 안에 답이 나올 것 같음.		* Network Flow 문제로 나와있는데, 그냥 적절한 가지치기를 통해서 dfs로 경로를 탐색해나가도 될 것 같음. n도 100밖에 안되고, 인접행렬 대신에 인접리스트를 사용해서 적당하게 탐색 공간을 줄이면 시간 안에 답이 나올 것 같음.

	* SP - 시작점, DP - 도착점, answer - SP에서 DP까지 경로의 최소 ~~Cost~~.		* SP - 시작점, DP - 도착점, answer - SP에서 DP까지 경로의 최소 비용.
	* SP에서 DP까지 가는 경로를 찾는 것은 DP에서 SP까지 가는 경로를 찾는 것과 같음.		* SP에서 DP까지 가는 경로를 찾는 것은 DP에서 SP까지 가는 경로를 찾는 것과 같음.
	* Stack에 담을 거니까 그냥 DP에서 SP까지 가는 경로를 찾자.		* Stack에 담을 거니까 그냥 DP에서 SP까지 가는 경로를 찾자.

	* 가지 치기 방법 : 내가 지금까지 구한 answer보다, 다른 노드로 연결 되는 ~~Edge의 Cost가~~ 작으면 탐색 할 필요가 없음.		* 가지 치기 방법 : 내가 지금까지 구한 answer보다, 다른 노드로 연결 되는 간선의 비용이 작으면 탐색 할 필요가 없음.
	=== 겪었던 문제 ===		=== 겪었던 문제 ===
	* 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.		* 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.

imported>trailblaze at 01:35, 18 February 2014

2014-02-18T01:35:30Z

← Older revision		Revision as of 01:35, 18 February 2014
Line 70:		Line 70:
	== 권영기 ==		== 권영기 ==
	=== 설명 ===		=== 설명 ===
	* Network Flow 문제로 나와있는데, 그냥 적절한 가지치기를 통해서 dfs로 경로를 탐색해나가도 될 것 같음. n도 100밖에 안되고, 인접행렬 대신에 인접리스트를 사용해서 적당하게 ~~Search Space를~~ 줄이면 시간 안에 답이 나올 것 같음.		* Network Flow 문제로 나와있는데, 그냥 적절한 가지치기를 통해서 dfs로 경로를 탐색해나가도 될 것 같음. n도 100밖에 안되고, 인접행렬 대신에 인접리스트를 사용해서 적당하게 탐색 공간을 줄이면 시간 안에 답이 나올 것 같음.

	* SP - 시작점, DP - 도착점, answer - SP에서 DP까지 경로의 최소 Cost.		* SP - 시작점, DP - 도착점, answer - SP에서 DP까지 경로의 최소 Cost.

imported>trailblaze at 01:34, 18 February 2014

2014-02-18T01:34:58Z

← Older revision		Revision as of 01:34, 18 February 2014
Line 82:		Line 82:

	* 첫 시도, 시간 초과.		* 첫 시도, 시간 초과.
	* 첫 번째 해결방법 : 다음 노드로 가는데 Cost가 높은 edge부터 탐색하자. adjList를 정렬함.		* 첫 번째 해결방법 : 0.9초에 끊어서, 그 때까지 얻은 가장 좋은 값을 출력하게 해보자.
			** 좋은 값을 주지 못함. 0.9초에 끊는 방법은 그만두기로 함.
			* 두 번째 해결방법 : 다음 노드로 가는데 Cost가 높은 edge부터 탐색하자. adjList를 정렬함.
	** 여전히 시간 초과		** 여전히 시간 초과
	* 두 번째 해결방법 : 소스를 보던 중, 의도했던 ~~가지치기~~ 코드가 잘못되었음을 발견.		* 세 번째 해결방법 : 소스를 보던 중, 의도했던 가지 치기 코드가 잘못되었음을 발견.
			** 가지 치기가 정상적으로 동작하니까, 잘 나옴. 첫 번째나 두 번째 시도가 별로 의미 없었음을 깨달음.
	=== 코드 ===		=== 코드 ===
	#include<iostream>		#include<iostream>

imported>trailblaze at 01:32, 18 February 2014

2014-02-18T01:32:36Z

← Older revision		Revision as of 01:32, 18 February 2014
Line 86:		Line 86:
	* 두 번째 해결방법 : 소스를 보던 중, 의도했던 가지치기 코드가 잘못되었음을 발견.		* 두 번째 해결방법 : 소스를 보던 중, 의도했던 가지치기 코드가 잘못되었음을 발견.
	=== 코드 ===		=== 코드 ===
			#include<iostream>
			#include<list>
			#include<vector>
			#include<stack>
			#include<queue>
			using namespace std;
			const int size = 120;
			const int VISITED = 1;
			const int UNVISTED = 0;
			class Node{
			public:
			int destination;
			int cost;

			Node() : destination(0), cost(0) { }
			Node(int destination, int cost) : destination(destination), cost(cost) { }
			};
			bool compare_Node(const Node& lhs, const Node& rhs){
			return lhs.cost > rhs.cost;
			}
			int n;
			int start, end1, answer = 0, answerCount = 9999999;
			int startClock, endClock;
			int adjMatrix[size][size];
			int checkNode[size];
			vector < list <Node> > adjList;
			queue < int > processQ;
			stack < int > currentPath, answerPath;
			void dfs(int currentPos, int minCost, int count){
			currentPath.push(currentPos);
			checkNode[currentPos] = VISITED;

			if(currentPos == start){
			if(answer < minCost){
			answer = minCost;
			answerCount = count;
			answerPath = currentPath;
			}
			else if(answer == minCost){
			if(answerCount > count){
			answerCount = count;
			answerPath = currentPath;
			}
			}
			return;
			}

			for(list<Node>::iterator it1 = adjList[currentPos].begin(); it1 != adjList[currentPos].end(); it1++){
			int nextNode = (*it1).destination;
			int cost = (*it1).cost;
			if(checkNode[nextNode] != VISITED && answer <= cost){
			dfs(nextNode, min(minCost, cost), count + 1);
			checkNode[nextNode] = UNVISTED;
			currentPath.pop();
			}
			}
			}
			int main(void)
			{
			startClock = clock();
			freopen("input.txt","r", stdin);
			freopen("output.txt","w", stdout);

			cin>>n;
			cin>>start>>end1;
			int s, e, cost;
			adjList.resize(n + 2);
			while(!cin.eof()){
			cin>>s>>e>>cost;
			adjMatrix[e][s] = cost;
			adjList[e].push_back(Node(s, cost));
			}
			for(int i = 1; i<=n; i++){
			adjList[i].sort(compare_Node);
			}
			dfs(end1, 999999999, 0);
			cout<<answer<<endl;
			while(!answerPath.empty()){
			cout<<answerPath.top()<<" ";
			answerPath.pop();
			}

			return 0;
			}

imported>trailblaze at 01:32, 18 February 2014

2014-02-18T01:32:08Z

← Older revision		Revision as of 01:32, 18 February 2014
Line 70:		Line 70:
	== 권영기 ==		== 권영기 ==
	=== 설명 ===		=== 설명 ===
			* Network Flow 문제로 나와있는데, 그냥 적절한 가지치기를 통해서 dfs로 경로를 탐색해나가도 될 것 같음. n도 100밖에 안되고, 인접행렬 대신에 인접리스트를 사용해서 적당하게 Search Space를 줄이면 시간 안에 답이 나올 것 같음.

			* SP - 시작점, DP - 도착점, answer - SP에서 DP까지 경로의 최소 Cost.
			* SP에서 DP까지 가는 경로를 찾는 것은 DP에서 SP까지 가는 경로를 찾는 것과 같음.
			* Stack에 담을 거니까 그냥 DP에서 SP까지 가는 경로를 찾자.

			* 가지 치기 방법 : 내가 지금까지 구한 answer보다, 다른 노드로 연결 되는 Edge의 Cost가 작으면 탐색 할 필요가 없음.
	=== 겪었던 문제 ===		=== 겪었던 문제 ===
	* 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.		* 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.

imported>trailblaze at 01:19, 18 February 2014

2014-02-18T01:19:26Z

← Older revision		Revision as of 01:19, 18 February 2014
Line 71:		Line 71:
	=== 설명 ===		=== 설명 ===
	=== 겪었던 문제 ===		=== 겪었던 문제 ===
			* 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.
			* 문제 푸는데 집중을 해야하는데 변수 이름, 클래스 이름에 신경을 많이 쓰게됨. 그렇다고 코드가 이쁘지도 않음.

			* 첫 시도, 시간 초과.
			* 첫 번째 해결방법 : 다음 노드로 가는데 Cost가 높은 edge부터 탐색하자. adjList를 정렬함.
			** 여전히 시간 초과
			* 두 번째 해결방법 : 소스를 보던 중, 의도했던 가지치기 코드가 잘못되었음을 발견.
	=== 코드 ===		=== 코드 ===

imported>trailblaze at 01:15, 18 February 2014

2014-02-18T01:15:40Z

← Older revision		Revision as of 01:15, 18 February 2014
Line 1:		Line 1:
			__TOC__

	e[http://183.106.113.109/30stair/virtual/virtual.php]		e[http://183.106.113.109/30stair/virtual/virtual.php]

Line 65:		Line 67:
	for i in path:		for i in path:
	print i,		print i,

			== 권영기 ==
			=== 설명 ===
			=== 겪었던 문제 ===
			=== 코드 ===