네트워크플로우

중요한 간선을 찾는 코드에서 prev2[next2.to] 가 되어있어야 하는데 prev2[curr2]로 되어 있는 것을 발견하지 못해 푸는데 오래 걸린 문제이다. 중요한 간선의 여부는 최대유량은 찾은 후에 입력 간선들 중에 u->v로 유량을 흘릴수 없는 경우 중요한 간선이라고 판단하였다. ...

시간초과가 계속해서 나는 것은 최적화 하면서 근근이 풀긴했는데, 속도가 많이 느리다. 자바로 풀 사람들 중에서 꼴등임 ㅎ 다른 정답자들의 풀이를 보니, 나는 에드몬드 카프 알고리즘을 이용해 풀었지만 빠르게 푼 사람들은 “디닉 알고리즘"이라는 것을 이용해서 풀었다. ...

어제 못 풀고 오늘에서야 푼 문제 정점을 1번만 지나는 조건을 만족하기 위해 정점을 분할하고 분할된 정점사이에 용량의 1의 간선을 추가해야 한다. 주의해야 할 것은 입력되는 간선들을 분할될 정점을 고려해 잘 이어주는 것이다. ...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 /** * */ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; /** * @author jaeji * */ class edge{ int to; int flow; int cap; edge rever; edge(){ this(0,0,0,null); } edge(int ar_to, int ar_flow, int ar_cap, edge ar_rever){ to = ar_to; flow = ar_flow; cap = ar_cap; rever = ar_rever; } int residu() { return cap-flow; } void addflow(int ar_flow) { flow+=ar_flow; rever.flow -=ar_flow; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //BufferedReader br = new BufferedReader( new FileReader("input.txt" ) ); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] prev = new int[402]; ArrayList[] adj = new ArrayList[402]; Queue<Integer> q = new LinkedList<Integer>(); int total = 0; for(int i=0;i<402;i++) { adj[i] = new ArrayList<edge>(); } for(int i=0;i<n;i++) { edge temp_edge = new edge(i,0,1,null); edge temp_rever_edge = new edge(400,0,0,temp_edge); temp_edge.rever = temp_rever_edge; adj[400].add(temp_edge); adj[i].add(temp_rever_edge); } for(int i=200;i<200+m;i++) { edge temp = new edge(401,0,1,null); edge temp_rever_edge = new edge(i,0,0,temp); temp.rever = temp_rever_edge; adj[i].add(temp); adj[401].add(temp_rever_edge); } int no = 0; int temp = 0; for(int i=0;i<n;i++) { st = new StringTokenizer(br.readLine()); no = Integer.parseInt(st.nextToken()); for(int j=0;j<no;j++) { temp = Integer.parseInt(st.nextToken())+199; edge temp_edge = new edge(temp,0,1,null); edge temp_rever_edge = new edge(i,0,0,temp_edge); temp_edge.rever = temp_rever_edge; adj[i].add(temp_edge); adj[temp].add(temp_rever_edge); } } int curr = 0; edge next = null; int S = 400; int E = 401; while(true) { edge[] path = new edge[402]; Arrays.fill(prev, -1); q.clear(); q.add(S); curr = 0; next = null; while(!q.isEmpty()) { // 소스에서 흐를수 있는 유량찾기 curr = q.poll(); for(int i=0;i<adj[curr].size();i++) { next = (edge) adj[curr].get(i); if(next.residu() > 0 && prev[next.to] == -1) { q.add(next.to); prev[next.to] = curr; path[next.to] = next; if(next.to == E) break; } } } if(prev[E] == -1) break; // 경로를 탐색 한 후 싱크로 가는 경로가 없는 경우 for(int i=E;i!=S;i=prev[i]) { path[i].addflow(1); } total += 1; } System.out.println(total); } }

드디어 네트워크플로우 처음에 목표한 알고리즘이 MCMF까지였기 때문에, 곧 결과에 쫓기듯 공부할 필요는 없을꺼같다. 배울 알고리즘이 참 많지만 사실 그런알고리즘은 내가 앞으로 쓸일이 있을까 하는 의문이 들어서 필요성을 느끼지 못하겠다. 그리고 필요하다면 그 때 배워서 사용하면 될꺼같기도 하다. 시험문제로 나온다면.. 그저 슬플수 밖에 ...