## Editorial for Bảo vệ

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int oo = 1 << 29;

struct edge
{
int x, y, cap, flow;
};

struct Flow
{
int n, S, T;
vector < vector <int> > a;
vector <int> cur, d;
vector <edge> e;

Flow() {}
Flow(int _n, int _S, int _T)
{
n = _n; S = _S; T = _T;
a = vector < vector <int> >(n + 1);
cur = vector <int>(n + 1);
d = vector <int>(n + 1);
}

void addEdge(int x, int y, int _cap)
{
edge e1 = {x, y, _cap, 0};
edge e2 = {y, x, 0, 0};
a[x].push_back(e.size()); e.push_back(e1);
a[y].push_back(e.size()); e.push_back(e2);
}

int bfs()
{
queue <int> q;
for (int i = 1; i <= n; i++) d[i] = -1;
q.push(S); d[S] = 0;
while (!q.empty() && d[T] < 0)
{
int x = q.front(); q.pop();
for (int i = 0; i < int(a[x].size()); i++)
{
int id = a[x][i], y = e[id].y;
if (d[y] < 0 && e[id].flow < e[id].cap)
q.push(y), d[y] = d[x] + 1;
}
}
return d[T] >= 0;
}

int dfs(int x, int val)
{
if (!val) return 0;
if (x == T) return val;
for (; cur[x] < int(a[x].size()); cur[x]++)
{
int id = a[x][cur[x]], y = e[id].y;
if (d[y] != d[x] + 1) continue;
int pushed = dfs(y, min(val, e[id].cap - e[id].flow));
if (pushed)
{
e[id].flow += pushed;
e[id ^ 1].flow -= pushed;
return pushed;
}
}
return 0;
}

int maxFlow()
{
int res = 0;
while (bfs())
{
for (int i = 1; i <= n; i++) cur[i] = 0;
while (1)
{
int val = dfs(S, oo);
if (!val) break;
res += val;
}
}
return res;
}

int minCut()
{
maxFlow();
int res = 0;
for (int x = 1; x <= n; x++)
if (d[x] >= 0)
for (int i = 0; i < int(a[x].size()); i++)
{
int id = a[x][i], y = e[id].y;
if (d[y] < 0) res += e[id].cap;
}
return res;
}
};

int main()
{
int n, x, y, z;
cin >> n;
Flow u(n, n, 1);
while (scanf("%d%d%d", &x, &y, &z) == 3)
cout << u.minCut() << endl;

}


#### Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
const int N = 5005;
struct edge {
int u, c, f;
edge(){}
edge(int u, int c): u(u), c(c), f(0) {}
};
vector<vector<edge> > g;
int n, s, t, trace[N];

void addEdge(int u, int v, int d) {
TR(g[u], i) if(i->u == v) { i->c += d; return; }
g[u].push_back(edge(v, d));
}
void addFlow(int u, int v, int d) { TR(g[u], i) if(i->u == v) { i->f += d; return; } }

void enter() {
scanf("%d", &n); g.resize(n); s = n-1; t = 0;
for(int u, v, d; scanf("%d%d%d",&u,&v,&d) == 3; ) {
--u; --v;
}
}

int FindPath() {
memset(trace, 0, sizeof trace); trace[s] = -1;
queue<pair<int, int> > q; q.push(pair<int, int>(s, 1000000000));
while(!q.empty()) {
int u = q.front().first, f = q.front().second; q.pop();
TR(g[u], i) if(trace[i->u] == 0 && i->c > i->f) {
trace[i->u] = u;
q.push(pair<int, int>(i->u, min(f, i->c - i->f)));
if(i->u == t) return min(f, i->c - i->f);
}
}
return -1;
}

void MaxFlow() {
int res = 0;
for(int inc; (inc = FindPath()) != -1; ) {
res += inc; int v = t;
do {
int u = trace[v];
v = u;
} while(v != s);
}
printf("%d\n", res);
}

int main() {
enter();
MaxFlow();
return 0;
}


#include <bits/stdc++.h>
const int N = 5001;
const int oo = 1000000009;
using namespace std;
int f[N][N], c[N][N], n, Q[N], T[N];
vector<int> a[N];

bool BFS() {
int l = 1, r = 1, i, u, v;
Q[1] = n;
for(i=1; i<=n; i++) T[i] = 0;
while (l<=r) {
u = Q[l++];
for(i=0; i<a[u].size(); i++) {
v = a[u][i];
if (T[v] == 0 && c[u][v]>f[u][v]) {
Q[++r] = v;
T[v] = u;
if (v == 1) return true;
}
}
}
return false;
}

void IncFlow() {
int v = 1, delta = oo, u;
while (v != n) {
u = T[v];
delta = min(delta, c[u][v] - f[u][v]);
v = u;
}
v = 1;
while (v != n) {
u = T[v];
f[u][v] += delta;
f[v][u] -= delta;
v = u;
}
}

int main()
{
//freopen("BAOVE.in", "r", stdin);
scanf("%d\n", &n); int u, v, w;
while (scanf("%d %d %d\n", &u, &v, &w) == 3) {
a[u].push_back(v); a[v].push_back(u);
c[u][v] += w;
}
while (BFS()) IncFlow();
int s = 0;
for(int i = 0; i<a[n].size(); i++)
s += f[n][a[n][i]];
printf("%d", s);
return 0;
}


#### Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{\$R+,Q+}
PROGRAM BAOVE;
CONST
fi='';
fo='';
maxn=5000;
max=10000;
oo=1000000000;
TYPE
rec=record v:integer; c:longint; end;
rec2=record u,v:integer; c:longint; end;
VAR
n:integer;
queue,cv,trace,degt,degn,th1,th2:array[1..maxn] of integer;
first,last:integer;
xet:array[1..maxn] of byte;
dt:array[1..maxn] of longint;
et,en:array[1..max] of rec;
ft:array[1..max] of longint;
s1,s2:array[1..maxn+1] of integer;
dscanh:array[1..max] of rec2;
m:integer;
f1,f2:text;
fl:longint;
Procedure OpenFiles;
Begin
Assign(f1,fi); Reset(f1);
Assign(f2,fo); Rewrite(f2);
End;
Procedure CloseFiles;
Begin
Close(f1); Close(f2);
End;
Begin
While not Eof(f1) do
begin
inc(m);
with dscanh[m] do
end;
End;
Procedure Trans;
Var
i:integer;
Begin
For i:=1 to m do
with dscanh[i] do
begin
inc(degt[u]);
inc(degn[v]);
end;
s1[1]:=1;
For i:=1 to n do
s1[i+1]:=s1[i]+degt[i];
s2[1]:=1;
For i:=1 to n do
s2[i+1]:=s2[i]+degn[i];
For i:=1 to m do
with dscanh[i] do
begin
et[s1[u]+th1[u]].v:=v;
et[s1[u]+th1[u]].c:=c;
inc(th1[u]);
en[s2[v]+th2[v]].v:=u;
en[s2[v]+th2[v]].c:=s1[u]+th1[u]-1;
inc(th2[v]);
end;
End;
Procedure Init;
Begin
Fillchar(dt,sizeof(dt),0);
dt[n]:=oo;
Fillchar(xet,sizeof(xet),0);
xet[n]:=1;
first:=1; last:=1;
queue[first]:=n;
trace[n]:=0;
End;
Function min(a,b:longint):longint;
Begin
if a<=b then min:=a else min:=b;
End;
Procedure FindPath;
Var
u,v,i:integer;
Begin
while first<=last do
begin
u:=queue[first]; inc(first);
for i:=s1[u] to s1[u+1]-1 do
with et[i] do
if (xet[v]=0) and (c-ft[i]>0) then
begin
xet[v]:=1;
inc(last); queue[last]:=v;
trace[v]:=u; cv[v]:=i;
dt[v]:=min(dt[u],c-ft[i]);
end;
for i:=s2[u] to s2[u+1]-1 do
with en[i] do
if (xet[v]=0) and (ft[c]>0) then
begin
xet[v]:=1;
inc(last); queue[last]:=v;
trace[v]:=-u; cv[v]:=c;
dt[v]:=min(dt[u],ft[c]);
end;
if dt[1]>0 then exit;
end;
End;
Procedure IncFlow;
Var
x,pre:integer;
Begin
x:=1;
repeat
pre:=trace[x];
if pre>0 then ft[cv[x]]:=ft[cv[x]]+dt[1]
else ft[cv[x]]:=ft[cv[x]]-dt[1];
x:=abs(pre);
until x=n;
End;
Procedure Solve;
Begin
fl:=0;
repeat
Init;
FindPath;
if dt[1]>0 then IncFlow;
fl:=fl+dt[1];
until dt[1]=0;
End;
Procedure WriteOutput;
Begin
Writeln(f2,fl);
End;
BEGIN
OpenFiles;
Trans;
Solve;
WriteOutput;
CloseFiles;
END.


#### Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 1111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;

void OPEN(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
}

// Dinic

#define maxn 5011
#define maxe 200011

struct Dinic{
int s, t, E, adj[maxe], cap[maxe], flow[maxe], next[maxe], last[maxn],
que[maxn], level[maxn], run[maxn];

void init(int _s, int _t){
s = _s; t = _t;
E = 0;
memset(last, -1, sizeof(last));
}

void add(int u, int v, int c1, int c2){
adj[E] = v; cap[E] = c1; flow[E] = 0; next[E] = last[u]; last[u] = E++;
adj[E] = u; cap[E] = c2; flow[E] = 0; next[E] = last[v]; last[v] = E++;
}

bool bfs(){
memset(level, -1, sizeof(level));
level[s] = 0;
int size = 0; que[size++] = s;
rep(i, size){
for(int u = que[i], e = last[u]; e != -1; e = next[e]){
if(level[v] == -1 && flow[e] < cap[e]){
level[v] = level[u] + 1;
que[size++] = v;
}
}
}
return level[t] != -1;
}

int dfs(int u, int bot){
if(u == t) return bot;
for(int &e = run[u]; e != -1; e = next[e]){
if(level[v] == level[u] + 1 && flow[e] < cap[e] && (delta = dfs(v, min(bot, cap[e] - flow[e]))) > 0){
flow[e] += delta;
flow[e ^ 1] -= delta;
return delta;
}
}
return 0;
}

ll maxflow(){
ll total = 0;
while(bfs()){
memcpy(run, last, sizeof(last));
for(int delta = dfs(s, oo); delta > 0; delta = dfs(s, oo)) total += delta;
}
}
} dinic;

int main(){
//OPEN();
int n, u, v, cost;
scanf("%d", &n);
dinic.init(n, 1);
while(scanf("%d %d %d", &u, &v, &cost) > 0){
}
printf("%lld\n",dinic.maxflow());
}


#### Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
const int INF=(int)1e9+7;
class DinicFlow {
private:
vector<int> capa,flow,next,point;
int n,m;
public:
DinicFlow() {
n=0;m=0;
}
DinicFlow(int n) {
this->n=n;
this->m=0;
dist=vector<int>(n+7);
q=vector<int>(n+7);
work=vector<int>(n+7);
}
void addedge(int u,int v,int c1,int c2) {
}
bool bfs(int s,int t) {
FOR(i,1,n) dist[i]=-1;
int sz=1;
q[0]=s;dist[s]=0;
REP(x,sz) {
int u=q[x];
if (dist[point[i]]<0 && flow[i]<capa[i]) {
dist[point[i]]=dist[u]+1;
q[sz]=point[i];
sz++;
}
}
return (dist[t]>=0);
}
int dfs(int s,int t,int f) {
if (s==t) return (f);
for (int &i=work[s];i>=0;i=next[i])
if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) {
int d=dfs(point[i],t,min(f,capa[i]-flow[i]));
if (d>0) {
flow[i]+=d;
flow[i^1]-=d;
return (d);
}
}
return (0);
}
int maxflow(int s,int t) {
int totflow=0;
while (bfs(s,t)) {
while (true) {
int d=dfs(s,t,INF);
if (d<=0) break;
totflow+=d;
}
}
return (totflow);
}
};
int n;
DinicFlow G;
void process(void) {
scanf("%d",&n);
G=DinicFlow(n);
int u,v,d;
cerr << 123 << endl;
printf("%d",G.maxflow(n,1));
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("tmp.txt","r",stdin);
#endif
process();
return 0;
}