- 技术博客
- dinic 板子洛谷p3376
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std
;
#define rep(i, l, r) for (int i = l; i <= r; i ++ )
#define clr(x, y) memset(x, y, sizeof (x))
const int INF
= 0x3f3f3f3f;
const int N
= 1e4+7, M
= 2e5 + 7;
int h
[M
], cnt
;
int n
, m
, s
, t
;
long long maxflow
;
struct Node
{
int to
, next
, val
;
}Edge
[M
];
void add(int u
, int v
, int val
)
{
Edge
[cnt
].to
= v
;
Edge
[cnt
].next
= h
[u
];
Edge
[cnt
].val
= val
;
h
[u
] = cnt
++;
}
int d
[M
], now
[M
];
queue
<int> q
;
bool bfs(){
clr(d
, 0);
while (q
.size()) q
.pop();
q
.push(s
);
d
[s
] = 1;
while (q
.size()){
int x
= q
.front(); q
.pop();
for (int i
= h
[x
]; ~i
; i
= Edge
[i
].next
){
int w
= Edge
[i
].val
, v
= Edge
[i
].to
;
if (w
&& !d
[v
]){
q
.push(v
);
d
[v
] = d
[x
] + 1;
if (v
== t
) return true;
}
}
}
return false;
}
int dinic(int x
, int flow
){
if(x
== t
) return flow
;
int rest
= flow
, k
, i
;
for (i
= h
[x
]; ~i
&& rest
; i
= Edge
[i
].next
){
int v
= Edge
[i
].to
, w
= Edge
[i
].val
;
if (w
&& d
[v
] == d
[x
] + 1)
{
k
= dinic(v
, min(rest
, w
));
if (!k
) d
[v
] = 0;
Edge
[i
].val
-= k
;
Edge
[i
^1].val
+= k
;
rest
-= k
;
}
}
return flow
- rest
;
}
int main
(){
clr(h
, -1);
scanf
("%d%d%d%d", &n
, &m
, &s
, &t
);
int i
;
rep(i
, 1, m
){
int u
, v
, w
;
scanf
("%d%d%d", &u
, &v
, &w
);
add(u
, v
, w
);
add(v
, u
, 0);
}
int flow
= 0;
while (bfs())
while (flow
= dinic(s
, INF
)) maxflow
+= flow
;
printf
("%lld\n", maxflow
);
return 0;
}
