Isap模板
如题= =自用模板

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
// Isap isap=new Isap();  
// isap.add_undiredge(x, y, u); 加无向边 即连两条
// int isap(int source, int sink, int N) 源点 汇点 顶点数
//注意n==0的情况
class Isap{
static int MAXN = (int) (1e5 + 7);
static int MAXM = (int) (2e5 + 7); //注意边的数目,因为连边是连两条/经常re
static int INF = 0x3f3f3f3f;
static Edge[]edge=new Edge[MAXM<<1];
static int[]head=new int[MAXN];
static int tot;
static int[]gap=new int[MAXN];
static int[]d=new int[MAXN];
static int[]cur=new int[MAXN];
static int[]que=new int[MAXN];
static int[]p=new int[MAXN];
static{
for(int i=0;i<(MAXM<<1);i++){
edge[i]=new Edge();
}
}
Isap(){
tot=0;
Arrays.fill(gap, 0);
Arrays.fill(head, -1);
}
void add_undiredge(int u, int v, int c)
{
edge[tot].to = v;
edge[tot].cap = c;
edge[tot].flow = 0;
edge[tot].next = head[u];
head[u] = tot++;
edge[tot].to = u;
edge[tot].cap = c;
edge[tot].flow = 0;
edge[tot].next = head[v];
head[v] = tot++;
}
void add_diredge(int u, int v, int c)
{
edge[tot].to = v;
edge[tot].cap = c;
edge[tot].flow = 0;
edge[tot].next = head[u];
head[u] = tot++;
edge[tot].to = u;
edge[tot].cap = 0;
edge[tot].flow = 0;
edge[tot].next = head[v];
head[v] = tot++;
}
void BFS(int source, int sink)
{
Arrays.fill(d, -1); //clr(d,-1);
Arrays.fill(gap,0); //clr(gap,0);
gap[0] = 1;
int front = 0, rear = 0;
d[sink] = 0;
que[rear++] = sink;
while (front != rear)
{
int u = que[front++];
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (d[v] != -1) continue;
que[rear++] = v;
d[v] = d[u] + 1;
gap[d[v]]++;
}
}
}
int isap(int source, int sink, int N)
{
BFS(source, sink);
//memcpy(cur, head, sizeof(head));
for(int i=0;i<MAXN;i++)cur[i]=head[i];
//cur=Arrays.copyOf(head, MAXN);
int top = 0, x = source, flow = 0;
while (d[source] < N)
{
if (x == sink)
{
int Min = INF, inser = 0;
for (int i = 0; i < top; ++i)
{
if (Min > edge[p[i]].cap - edge[p[i]].flow)
{
Min = edge[p[i]].cap - edge[p[i]].flow;
inser = i;
}
}
for (int i = 0; i < top; ++i)
{
edge[p[i]].flow += Min;
edge[p[i] ^ 1].flow -= Min;
}
flow += Min;
top = inser;
x = edge[p[top] ^ 1].to;
continue;
}
int ok = 0;
for (int i = cur[x]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].cap > edge[i].flow && (d[v] + 1) == d[x])
{
ok = 1;
cur[x] = i;
p[top++] = i;
x = edge[i].to;
break;
}
}
if (ok==0)
{
int Min = N;
for (int i = head[x]; i != -1; i = edge[i].next)
{
if (edge[i].cap > edge[i].flow && d[edge[i].to] < Min)
{
Min = d[edge[i].to];
cur[x] = i;
}
}
if (--gap[d[x]] == 0) break;
gap[d[x] = Min + 1]++;
if (x != source) x = edge[p[--top] ^ 1].to;
}
}
return flow;
}
}
class Edge{
int to,next,cap,flow;
}