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
| #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 INF (long long) 1e15 #define MAX_N 202 #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,k,u,v; ll seen[MAX_N], match[MAX_N]; vll adj[MAX_N];
ll dfs(ll u, ll s) { seen[u] = s; for(auto& v : adj[u]) { if(match[v] == -1 or (seen[match[v]] != s and dfs(match[v], s))) { match[v] = u; return 1; } } return 0; }
ll solve() { ll res = 0; memset(match, -1, sizeof match); memset(seen, -1, sizeof seen); for(ll i = 1; i<= n; i++) { res += dfs(i,i); } return n + m - res; }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>k; while(k--) { cin>>u>>v; adj[u].push_back(v); }
cout<<solve();
return 0; }
|