1.1. 설명 ¶
- 기본적인 아이디어는 노드를 하나씩 제거하는 것
- 루프가 없고 한 방향으로만 흘러가기 때문에 가능
- 루프가 없고 한 방향으로만 흘러가기 때문에 가능
- 들어오는 edge가 없는 node를 제거하고 그 node에서 나가는 edge와 연결된 node들의 최대 흐를 수 있는 양을 확인 후 변경
- 현재 node에서 흐를 수 있는 양보다 크면 그 양을 갱신하고 parent를 이전 노드로 지정
- 같아도 변경하지 않음.
- 최대로 흐를 수 있는 양이 같더라도 먼저 계산한 것이 더 최단거리임
- 최대로 흐를 수 있는 양이 같더라도 먼저 계산한 것이 더 최단거리임
- 현재 node에서 흐를 수 있는 양보다 크면 그 양을 갱신하고 parent를 이전 노드로 지정
- path는 도착지점부터 parent 노드를 쫒아가면 됨.
1.2. 겪었던 문제 ¶
- 처음에는 하나씩 지워나간다고 생각해서 검사할 node를 int 형으로 기록했으나, 가장 초기에는 지워야 하는 node가 시작점 하나만 있는 것이 아닌 것을 알게 되어 stack으로 변경.
1.3. 코드 ¶
points = int(raw_input()) point_current, point_end = [int(i) for i in raw_input().split()] graph = [[-1] * (points + 1) for i in range(points + 1)] point_in = [0] * (points + 1) point_parent = [0] * (points + 1) point_parent[point_current] = -1 point_flow = [0] * (points + 1) point_flow[point_current] = 99999 while True: try: input_data = [int(i) for i in raw_input().split()] if not input_data: break graph[input_data[0]][input_data[1]] = input_data[2] point_in[input_data[1]] += 1 except EOFError: break stack = [point_current] for i in range(1, points + 1): if point_in[i] == 0 and i != point_current: stack.append(i) while stack: point_current = stack.pop() for i in range(points + 1): flow = min(graph[point_current][i], point_flow[point_current]) if flow != -1: graph[point_current][i] = -1 if flow > point_flow[i]: point_flow[i] = flow point_parent[i] = point_current point_in[i] -= 1 if point_in[i] == 0: stack.append(i) print point_flow[point_end] path = [] point_current = point_end while point_current != -1: path.append(point_current) point_current = point_parent[point_current] path.reverse() for i in path: print i,
2.1. 설명 ¶
- Network Flow 문제로 나와있는데, 그냥 적절한 가지치기를 통해서 dfs로 경로를 탐색해나가도 될 것 같음. n도 100밖에 안되고, 인접행렬 대신에 인접리스트를 사용해서 적당하게 탐색 공간을 줄이면 시간 안에 답이 나올 것 같음.
- SP - 시작점, DP - 도착점, answer - SP에서 DP까지 경로의 최소 Cost.
- SP에서 DP까지 가는 경로를 찾는 것은 DP에서 SP까지 가는 경로를 찾는 것과 같음.
- Stack에 담을 거니까 그냥 DP에서 SP까지 가는 경로를 찾자.
- 가지 치기 방법 : 내가 지금까지 구한 answer보다, 다른 노드로 연결 되는 Edge의 Cost가 작으면 탐색 할 필요가 없음.
2.2. 겪었던 문제 ¶
- 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.
- 문제 푸는데 집중을 해야하는데 변수 이름, 클래스 이름에 신경을 많이 쓰게됨. 그렇다고 코드가 이쁘지도 않음.
- 첫 시도, 시간 초과.
- 첫 번째 해결방법 : 0.9초에 끊어서, 그 때까지 얻은 가장 좋은 값을 출력하게 해보자.
- 좋은 값을 주지 못함. 0.9초에 끊는 방법은 그만두기로 함.
- 두 번째 해결방법 : 다음 노드로 가는데 Cost가 높은 edge부터 탐색하자. adjList를 정렬함.
- 여전히 시간 초과
- 세 번째 해결방법 : 소스를 보던 중, 의도했던 가지 치기 코드가 잘못되었음을 발견.
- 가지 치기가 정상적으로 동작하니까, 잘 나옴. 첫 번째나 두 번째 시도가 별로 의미 없었음을 깨달음.
2.3. 코드 ¶
#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;
}
