二分图的模板题 不过这题题意 我纠结了好久 不知道是不是我对二分图不熟悉的原因
这题就是说 有ｎ＋ｍ个人参加会议 要在这ｎ＋ｍ中进行通话 求最少的连接数 就是每个人都得被连接上 这样求最大匹配就是了 再用总结点数减匹配的
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<int>ed[];
int n,m,k,vis[],link[];
int find(int u)
{
int i;
for(i = ; i < (int)ed[u].size() ; i++)
{
int v = ed[u][i];
if(vis[v])
continue;
vis[v] = ;
if(link[v]==||find(link[v]))
{
link[v] = u;
return ;
}
}
return ;
}
int main()
{
int i,u,v;
scanf("%d%d%d",&n,&m,&k);
for(i = ; i <= k ; i++)
{
scanf("%d%d",&u,&v);
ed[u].push_back(v+n);
ed[v+n].push_back(u);
}
int num=;
for(i = ; i <= n ; i++)
{
memset(vis,,sizeof(vis));
if(find(i))
num++;
}
printf("%d\n",n+m-*num+num);
return ;
}