반응형
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
|
package 개인공부;
import java.util.ArrayList;
import 개인공부.포드폴커슨_인접리스트.Edge;
public class 포드폴커슨_인접리스트 {
static class Edge {
int target, capacity, flow;
// 역방향 정보를 넣을 곳
Edge reverse;
public Edge(int target, int capacity, int flow) {
super();
this.target = target;
this.capacity = capacity;
this.flow = flow;
}
int residualCapacity() {
return this.capacity - this.flow;
}
// 유량을 흘려보내기 a->b 로 흘려보냇다면 b->a 로는 빠져나가야한다.
void push(int amt) {
this.flow += amt;
}
}
static final int MAX_V = 1000;
static ArrayList<Edge> adj[] = new ArrayList[MAX_V];
// u에서 v로 가는 간선을 추가한다.
static void addEdge(int u, int v, int capacity) {
// u->v로 가는 용량과 유량은 그대로 설정한다. 처음생성했기에 flow는 0이다
Edge uv = new Edge(v, capacity, 0);
// v->u로 가는경우 용량은 0이다
Edge vu = new Edge(u, 0, 0);
// 반대로 가는 간선을 서로 추가해준다.
uv.reverse = vu;
vu.reverse = uv;
}
public static void main(String[] args) {
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'Algorithm' 카테고리의 다른 글
트라이(Trie) : JAVA / 백준 5052 (0) | 2020.04.26 |
---|---|
이분 매칭 알고리즘 ( JAVA),열혈강호1,2,3 문제 (0) | 2020.04.25 |
네트워크 유량 ( network flow) / 포드 - 풀커슨 알고리즘 JAVA (2) | 2020.04.19 |
KMP 알고리즘 (0) | 2020.04.10 |
투 포인터 알고리즘 (0) | 2020.04.06 |