四种算法随便选！！！
#include <bits/stdc++.h>
#define int long long
using namespace std ;
const int MAXN = 1205 ;
const long long INF = (1LL << 62) ;
struct Edge { int to , cap , rev ; } ;
vector<Edge> g[MAXN] ;
int n , m , s , t ;
const int MAXM = 120000 + 5 ;
int eu[MAXM] , ev[MAXM] ; long long ew[MAXM] ;
int max (int a , int b) {return a > b ? a : b ;
}
void build_graph () {for (int i = 1 ; i <= n ; i ++) {g[i].clear() ;}int avg = max(4 , (int) (m / max(1, n)) + 2) ;for (int i = 1 ; i <= n ; i ++) g[i].reserve(avg) ;for (int i = 1 ; i <= m ; i ++) {int u = eu[i] , v = ev[i] ; long long w = ew[i] ;g[u].push_back({v , (int) w , (int) g[v].size()}) ;g[v].push_back({u , 0 , (int) g[u].size() - 1}) ;}
}/* ------------------ Dinic ------------------ */
int disD[MAXN] , curD[MAXN] ;
bool bfsD () {memset(disD , -1 , sizeof(disD)) ;queue<int> q ;disD[s] = 0 ; q.push(s) ;while (! q.empty()) {int u = q.front() ; q.pop() ;for (auto &e : g[u]) {if (e.cap > 0 && disD[e.to] == -1) {disD[e.to] = disD[u] + 1 ;q.push(e.to) ;}}}return disD[t] != -1 ;
}
int dfsD (int u , int flow) {if (! flow) return 0 ;if (u == t) return flow ;for (int &i = curD[u] ; i < (int) g[u].size() ; i ++) {Edge &e = g[u][i] ;if (e.cap > 0 && disD[e.to] == disD[u] + 1) {int got = dfsD(e.to , (int) min((long long)flow , (long long)e.cap)) ;if (got > 0) {e.cap -= got ;g[e.to][e.rev].cap += got ;return got ;}}}return 0 ;
}
long long run_dinic () {long long flow = 0 ;while (bfsD()) {memset(curD , 0 , sizeof(curD)) ;while (int pushed = dfsD(s , (int)INF)) flow += pushed ;}return flow ;
}/* ------------------ ISAP ------------------ */
int disI[MAXN] , curI[MAXN] , gapI[MAXN] ;
void bfs_from_t () {for (int i = 1 ; i <= n ; i ++) disI[i] = -1 ;queue<int> q ;disI[t] = 0 ; q.push(t) ;while (! q.empty()) {int u = q.front() ; q.pop() ;for (auto &e : g[u]) {if (g[e.to][e.rev].cap > 0 && disI[e.to] == -1) {disI[e.to] = disI[u] + 1 ;q.push(e.to) ;}}}for (int i = 1 ; i <= n ; i ++) if (disI[i] == -1) disI[i] = n ;for (int i = 0 ; i <= n ; i ++) gapI[i] = 0 ;for (int i = 1 ; i <= n ; i ++) gapI[disI[i]] ++ ;
}
int dfsI (int u , int flow) {if (u == t) return flow ;int used = 0 ;for (int &i = curI[u] ; i < (int) g[u].size() ; i ++) {Edge &e = g[u][i] ;if (e.cap > 0 && disI[e.to] + 1 == disI[u]) { int got = dfsI(e.to , (int) min((long long)(flow - used) , (long long)e.cap)) ;if (got > 0) {e.cap -= got ;g[e.to][e.rev].cap += got ;used += got ;if (used == flow) return used ;}}}gapI[disI[u]] -- ;if (gapI[disI[u]] == 0) { disI[s] = n ;}disI[u] ++ ;if (disI[u] > n) disI[u] = n ;gapI[disI[u]] ++ ;curI[u] = 0 ;return used ;
}
long long run_isap () {bfs_from_t() ;memset(curI , 0 , sizeof(curI)) ;long long flow = 0 ;while (disI[s] < n) flow += dfsI(s , (int)INF) ;return flow ;
}/* ------------------ ID ------------------ */
int disID[MAXN] , curID[MAXN] ;
bool bfsID () {memset(disID , -1 , sizeof(disID)) ;queue<int> q ;disID[s] = 0 ; q.push(s) ;while (! q.empty()) {int u = q.front() ; q.pop() ;for (auto &e : g[u]) if (e.cap > 0 && disID[e.to] == -1) {disID[e.to] = disID[u] + 1 ;q.push(e.to) ;}}return disID[t] != -1 ;
}
int dfsID (int u , int flow) {if (! flow) return 0 ;if (u == t) return flow ;for (int &i = curID[u] ; i < (int) g[u].size() ; i ++) {Edge &e = g[u][i] ;if (e.cap > 0 && disID[e.to] == disID[u] + 1) {int got = dfsID(e.to , (int) min((long long)flow , (long long)e.cap)) ;if (got > 0) {e.cap -= got ;g[e.to][e.rev].cap += got ;return got ;}}}disID[u] = -1 ;return 0 ;
}
long long run_idinic () {long long flow = 0 ;while (bfsID()) {memset(curID , 0 , sizeof(curID)) ;while (int pushed = dfsID(s , (int)INF)) flow += pushed ;}return flow ;
}/* ------------------ HLPP ------------------ */
int hH[MAXN] , ex[MAXN] , curH[MAXN] ;
vector<int> bucket[2 * MAXN] ; // 高度可能到 2*n
int maxH ;
long long run_hlpp () {// initfor (int i = 0 ; i <= 2 * n ; i ++) bucket[i].clear() ;for (int i = 1 ; i <= n ; i ++) { hH[i] = 0 ; ex[i] = 0 ; curH[i] = 0 ; }// preflowhH[s] = n ;for (auto &e : g[s]) {if (e.cap > 0) {int f = e.cap ;e.cap = 0 ;g[e.to][e.rev].cap += f ;ex[e.to] += f ;}}maxH = 0 ;for (int i = 1 ; i <= n ; i ++) if (i != s && i != t && ex[i] > 0) {bucket[hH[i]].push_back(i) ;maxH = max(maxH , hH[i]) ;}// 主循环：从最高桶取点 dischargewhile (maxH >= 0) {if (bucket[maxH].empty()) { maxH -- ; continue ; }int u = bucket[maxH].back() ; bucket[maxH].pop_back() ;// discharge uwhile (ex[u] > 0) {if (curH[u] < (int) g[u].size()) {Edge &e = g[u][curH[u]] ;if (e.cap > 0 && hH[u] == hH[e.to] + 1) {int f = (int) min((long long)ex[u] , (long long)e.cap) ;int prev = ex[e.to] ;e.cap -= f ;g[e.to][e.rev].cap += f ;ex[u] -= f ;ex[e.to] += f ;if (e.to != s && e.to != t && prev == 0) {bucket[hH[e.to]].push_back(e.to) ;maxH = max(maxH , hH[e.to]) ;}} else curH[u] ++ ;} else {// relabelint minh = INT_MAX ;for (auto &e : g[u]) if (e.cap > 0) minh = min(minh , hH[e.to]) ;if (minh == INT_MAX) { hH[u] = 2 * n ; } else { hH[u] = minh + 1 ; }curH[u] = 0 ;}}}return ex[t] ;
}/* ------------------ 主程序和模式选择 ------------------ */
signed main () {ios::sync_with_stdio(false) ;cin.tie(NULL) ; cout.tie(NULL) ;int mode = 4 ; // 改 mode: 1/2/3/4cin >> n >> m >> s >> t ;for (int i = 1 ; i <= m ; i ++) {int uu , vv ; long long ww ;cin >> uu >> vv >> ww ;eu[i] = uu ; ev[i] = vv ; ew[i] = ww ;}build_graph() ;long long ans = 0 ;if (mode == 1) ans = run_dinic() ;else if (mode == 2) ans = run_isap() ;else if (mode == 3) ans = run_idinic() ;else if (mode == 4) ans = run_hlpp() ;cout << ans << '\n' ;return 0 ;
}