|
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071 |
- #include <bits/stdc++.h>
- #define pb push_back
- #define int long long
- using namespace std ;
- const long long MAXN = 1e9+1 ;
- const int N = (int)(2e4) + 256 ;
- int n , m , timer , used[N] , lim ;
- struct edge{
- int v , u , c , f ;
- };
- vector <edge> e ;
- vector <int> g[N] ;
- inline void addEdge(int v , int u , int c )
- {
- e.pb({v,u,c,0}) ;
- g[v].pb(e.size()-1) ;
- e.pb({u,v,0,0}) ;
- g[u].pb(e.size()-1) ;
- }
- int dfs ( int v , int t , int pushed = MAXN , int p = -1 )
- {
- if (used[v] == timer || pushed < lim) return 0;
- if (!pushed || v == t) return pushed;
-
- used[v] = timer ;
- for ( int i = 0 ; i < g[v].size() ; ++i )
- {
- int id = g[v][i] ;
- int to = e[id].u , f = e[id].f , c = e[id].c ;
- if ( p == to || f == c ) continue ;
- int nxt = dfs ( to , t , min ( pushed , c - f) , v);
- if ( nxt > 0 )
- {
- e[id].f += nxt ;
- e[id^1].f -= nxt ;
- return nxt ;
- }
- }
- return 0 ;
- }
- inline int fordf(int s,int t)
- {
- int res = 0 ;
- lim = 1 << 30 ;
- while ( lim > 0 )
- {
- ++timer ;
- int pushed = dfs(s,t) ;
- if ( !pushed )
- {
- lim >>= 1 ;
- continue ;
- }
- res += pushed ;
- }
- return res ;
- }
- main()
- {
- freopen("flow.in","r",stdin) ;
- freopen("flow.out","w",stdout) ;
- cin >> n >> m ;
- for ( int i = 0 ; i < m ; ++i )
- {
- int x , y , c ;
- cin >> x >> y >> c ;
- addEdge(x,y,c) ;
- }
- cout << fordf(1,n) << endl ;
- return 0 ;
- }
|