有向图匹配
<pre><code class="language-cpp">#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int maxn = 105;
int n, m, k;
vector<set<int>> mp(maxn);
int vis[maxn], pre[maxn];
int c = 0;
bool found(int u, int t){
vis[u] = t;
for(set<int>::iterator i = mp[u].begin(); i != mp[u].end(); i++){
int v = *i;
if(vis[v] == t) continue;
vis[v] = t;
if(pre[v] == 0 || found(pre[v], t)){
pre[v] = u;
return true;
}
}
return false;
}
//处理有向图的匹配，只一个点只能指向另一个点的匹配
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; i++){
int u, v;
scanf("%d%d", &u, &v);
mp[u].insert(v+n); //有向图要分成
}
for(int i = 1; i <= k; i++){
scanf("%lld%lld", &query[i].first, &query[i].second);
}
for(int i = 1; i <= n; i++){ //这里是重点
if(found(i, i)) c++;
}
}</code></pre>