View source for AlgorithmStudy/2014/virtual

__TOC__

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

== 조영준 ==

=== 설명 ===
* 기본적인 아이디어는 '''노드를 하나씩 제거'''하는 것
** 루프가 없고 한 방향으로만 흘러가기 때문에 가능
* 들어오는 edge가 없는 node를 제거하고 그 node에서 나가는 edge와 연결된 node들의 최대 흐를 수 있는 양을 확인 후 변경
** 현재 node에서 흐를 수 있는 양보다 크면 그 양을 갱신하고 parent를 이전 노드로 지정
** 같아도 변경하지 않음.
** 최대로 흐를 수 있는 양이 같더라도 먼저 계산한 것이 더 최단거리임
* path는 도착지점부터 parent 노드를 쫒아가면 됨. 
=== 겪었던 문제 ===
* 처음에는 하나씩 지워나간다고 생각해서 검사할 node를 int 형으로 기록했으나, 가장 초기에는 지워야 하는 node가 시작점 하나만 있는 것이 아닌 것을 알게 되어 stack으로 변경.
=== 코드 ===
* Python2
* [http://183.106.113.109/displaysrc.php?id=1178830]
 points = int(raw_input())
 point_current, point_end = &#91;int(i) for i in raw_input().split()&#93;
  
 graph = &#91;&#91;-1&#93; * (points + 1) for i in range(points + 1)&#93;
 point_in = &#91;0&#93; * (points + 1)
 point_parent = &#91;0&#93; * (points + 1)
 point_parent&#91;point_current&#93; = -1
 point_flow = &#91;0&#93; * (points + 1)
 point_flow&#91;point_current&#93; = 99999
  
 while True:
     try:
         input_data = &#91;int(i) for i in raw_input().split()&#93;
         if not input_data:
             break
         graph&#91;input_data&#91;0&#93;&#93;&#91;input_data&#91;1&#93;&#93; = input_data&#91;2&#93;
         point_in&#91;input_data&#91;1&#93;&#93; += 1
     except EOFError:
         break
  
 stack = &#91;point_current&#93;
 for i in range(1, points + 1):
     if point_in&#91;i&#93; == 0 and i != point_current:
         stack.append(i)
  
 while stack:
     point_current = stack.pop()
     for i in range(points + 1):
         flow = min(graph&#91;point_current&#93;&#91;i&#93;, point_flow&#91;point_current&#93;)
         if flow != -1:
             graph&#91;point_current&#93;&#91;i&#93; = -1
             if flow &gt; point_flow&#91;i&#93;:
                 point_flow&#91;i&#93; = flow
                 point_parent&#91;i&#93; = point_current
             point_in&#91;i&#93; -= 1
             if point_in&#91;i&#93; == 0:
                 stack.append(i)
  
 print point_flow&#91;point_end&#93;
  
 path = &#91;&#93;
 point_current = point_end
 while point_current != -1:
     path.append(point_current)
     point_current = point_parent&#91;point_current&#93;
  
 path.reverse()
 for i in path:
     print i,

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

* SP - 시작점, DP - 도착점, answer - SP에서 DP까지 경로의 최소 비용.
* SP에서 DP까지 가는 경로를 찾는 것은 DP에서 SP까지 가는 경로를 찾는 것과 같음.
* Stack에 담을 거니까 그냥 DP에서 SP까지 가는 경로를 찾자.
 
* 가지 치기 방법 : 내가 지금까지 구한 answer보다, 다른 정점으로 연결 되는 간선의 비용이 작으면 탐색 할 필요가 없음.
=== 겪었던 문제 ===
* 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.
* 문제 푸는데 집중을 해야하는데 변수 이름, 클래스 이름에 신경을 많이 쓰게됨. 그렇다고 코드가 이쁘지도 않음.
 
* 첫 시도, 시간 초과.
* 첫 번째 해결방법 : 0.9초에 끊어서, 그 때까지 얻은 가장 좋은 값을 출력하게 해보자.
** 좋은 값을 주지 못함. 0.9초에 끊는 방법은 그만두기로 함.
* 두 번째 해결방법 : 다음 정점으로 가는데 비용이 높은 간선부터 탐색하자. adjList를 정렬함. 
** 여전히 시간 초과
* 세 번째 해결방법 : 코드를 보던 중, 의도했던 가지 치기 코드가 잘못되었음을 발견.
** 가지 치기가 정상적으로 동작하니까, 잘 나옴. 첫 번째나 두 번째 시도가 별로 의미 없었음을 깨달음.
=== 코드 ===
 #include&lt;iostream&gt;
 #include&lt;list&gt;
 #include&lt;vector&gt;
 #include&lt;stack&gt;
 #include&lt;queue&gt;
 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&amp; lhs, const Node&amp; rhs){
 	return lhs.cost &gt; rhs.cost;
 }
 int n;
 int start, end1, answer = 0, answerCount = 9999999;
 int startClock, endClock;
 int adjMatrix&#91;size&#93;&#91;size&#93;;
 int checkNode&#91;size&#93;;
 vector &lt; list &lt;Node&gt; &gt; adjList;
 queue &lt; int &gt; processQ;
 stack &lt; int &gt; currentPath, answerPath;
 void dfs(int currentPos, int minCost, int count){
 	currentPath.push(currentPos);
 	checkNode&#91;currentPos&#93; = VISITED;
 
 	if(currentPos == start){
 		if(answer &lt; minCost){
 			answer = minCost;
 			answerCount = count;
 			answerPath = currentPath;
 		}
 		else if(answer == minCost){
 			if(answerCount &gt; count){
 				answerCount = count;
 				answerPath = currentPath;
 			}
 		}
 		return;
 	}
 
 	for(list&lt;Node&gt;::iterator it1 = adjList&#91;currentPos&#93;.begin(); it1 != adjList&#91;currentPos&#93;.end(); it1++){
 		int nextNode = (*it1).destination;
 		int cost = (*it1).cost;
 		if(checkNode&#91;nextNode&#93; != VISITED &amp;&amp; answer &lt;= cost){
 			dfs(nextNode, min(minCost, cost), count + 1);
 			checkNode&#91;nextNode&#93; = UNVISTED;
 			currentPath.pop();
 		}	
 	}
 }
 int main(void)
 {
 	startClock = clock();
 	freopen("input.txt","r", stdin);
 	freopen("output.txt","w", stdout);
 
 	cin&gt;&gt;n;
 	cin&gt;&gt;start&gt;&gt;end1;
 	int s, e, cost;
 	adjList.resize(n + 2);
 	while(!cin.eof()){
 		cin&gt;&gt;s&gt;&gt;e&gt;&gt;cost;
 		adjMatrix&#91;e&#93;&#91;s&#93; = cost;
 		adjList&#91;e&#93;.push_back(Node(s, cost));
 	}
 	for(int i = 1; i&lt;=n; i++){
 		adjList&#91;i&#93;.sort(compare_Node);
 	}
 	dfs(end1, 999999999, 0);
 	cout&lt;&lt;answer&lt;&lt;endl;
 	while(!answerPath.empty()){
 		cout&lt;&lt;answerPath.top()&lt;&lt;" ";
 		answerPath.pop();
 	}
 	
 	return 0;
 }