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
| #include <bits/stdc++.h>
#pragma optimization_level 3 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops")
#define MAX_N 505 #define ll long long #define pll pair<ll, ll> #define vpll vector<pll> #define vll vector<ll> #define vall3 vector<array<ll,3>> #define vs vector<string> #define vvll vector<vll> #define all(a) begin(a), end(a) using namespace std;
ll n,m; vector<ll> adj[MAX_N]; ll path[MAX_N], cap[MAX_N][MAX_N], flo[MAX_N][MAX_N];
bool bfs(ll u, ll v) { memset(path, 0, sizeof path); queue<ll> q; q.push(u); while(!q.empty() and !path[v]) { auto n = q.front(); q.pop(); for(auto& m : adj[n]) { if(cap[n][m] - flo[n][m] > 0 and !path[m]) { path[m] = n; q.push(m); } } } return path[v] != 0; }
ll solve(vall3& edges, ll u, ll v) { for(auto& [u, v, w] : edges) { adj[u].push_back(v); adj[v].push_back(u); cap[u][v] += w; cap[v][u] += w; flo[u][v] += w; } ll sum = 0; while(bfs(u,v)) { ll vv = v, mi = INT_MAX; while(vv != u) { auto uu = path[vv]; mi = min(mi, cap[uu][vv] - flo[uu][vv]); vv = uu; } vv = v; while(vv != u) { auto uu = path[vv]; flo[uu][vv] += mi; flo[vv][uu] -= mi; vv = uu; } sum += mi; }
return sum; }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m; ll u,v; vall3 edges; while(m--) { cin>>v>>u; edges.push_back({u,v,1}); } cout<<solve(edges, 1,2);
return 0; }
|