백준알고리즘 5651번 - 완전 중요한 간선

  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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

import java.awt.Point;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
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;

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());
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();

		// 테스트 케이스 K번 반복한다
		for (int i = 0; i < K; i++) {

			int N = sc.nextInt();
			int M = sc.nextInt();
			edge f_edge = null;
			edge b_edge = null;
			int u = 0, v = 0, c = 0;
			int S = 0;
			int E = N - 1;
			int mf = 0;
			int cnt = 0;
			ArrayList<Point> edge_list = new ArrayList<Point>();

			// 정점의 수만큼 인접리스트 생성
			ArrayList<edge>[] adj = new ArrayList[N];
			for (int j = 0; j < N; j++) {
				adj[j] = new ArrayList<edge>();
			}

			// 간선 입력 받기
			for (int j = 0; j < M; j++) {
				u = sc.nextInt() - 1;
				v = sc.nextInt() - 1;
				edge_list.add(new Point(u,v));
				c = sc.nextInt();

				f_edge = new edge(v, 0, c, null);
				b_edge = new edge(u, 0, 0, f_edge);
				f_edge.rever = b_edge;

				adj[u].add(f_edge);
				adj[v].add(b_edge);
			}

			// 최대 유량 찾기, 에드몬드 카프
			while (true) {
				int[] prev = new int[N];
				edge[] path = new edge[N];
				Arrays.fill(prev, -1);
				Queue<Integer> q = new LinkedList<Integer>();
				q.add(S);

				label1: while (!q.isEmpty() && prev[E] == -1) {
					int curr = q.poll();
					for (int j = 0; j < adj[curr].size(); j++) {
						edge next = adj[curr].get(j);
						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 label1;
						}
					}
				}

				// 입력 간선 리스트 중에서 중요한 간선을 확인함
				if (prev[E] == -1) {
					
					for(int j=0;j<edge_list.size();j++) {
						Point temp = new Point();
						temp = edge_list.get(j);
						int S2 = temp.x;
						int E2 = temp.y;
						int[] prev2 = new int[N];
						Arrays.fill(prev2, -1);
						Queue<Integer> q2 = new LinkedList<Integer>();
						q2.add(S2);
						label2: while (!q2.isEmpty()) {
							int curr2 = q2.poll();
							for (int l = 0; l < adj[curr2].size(); l++) {
								edge next2 = adj[curr2].get(l);
								if ( next2.residu() > 0 && prev2[next2.to] == -1) {
									q2.add(next2.to);
									prev2[next2.to] = curr2;
									if(prev2[E2] == next2.to) break label2;
								}
							}
						}

						if (prev2[E2] == -1)
							cnt++;
						
					}
					
					System.out.println(cnt);
					break;

				}

				int flow = Integer.MAX_VALUE;
				for (int k = E; k != S; k = prev[k])
					flow = Math.min(flow, path[k].residu());

				for (int k = E; k != S; k = prev[k])
					path[k].addflow(flow);

				mf += flow;

			}

		}

	}
}