时间复杂度 O(sqrt(n) * e)
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define eps 1e-8
using namespace std;
const int maxd = 3e5+10;
const int inf = 1e9;
int cx[maxd],cy[maxd],dx[maxd],dy[maxd],used[maxd];
vector<int> G[maxd];
int n,m,dis;
int bfs()
{
queue<int> que;
dis = inf;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=1;i<=n;i++)
{
if(cx[i] == -1)
{
que.push(i);
dx[i] = 0;
}
}
while(!que.empty())
{
int x = que.front(); que.pop();
if(dx[x] > dis) break;
for(int v: G[x])
if(dy[v] == -1)
{
dy[v] = dx[x] + 1;
if(cy[v] == -1) dis = dy[v];
else
{
dx[cy[v]] = dy[v]+1;
que.push(cy[v]);
}
}
}
return dis!=inf;
}
bool dfs(int x)
{
for(int v : G[x])
{
if(!used[v] && dy[v] == dx[x]+1)
{
used[v] = true;
if(cy[v] != -1 && dy[v] == dis) continue;
if(cy[v] == -1 || dfs(cy[v]))
{
cy[v] = x;
cx[x] = v;
return true;
}
}
}
return false;
}
int maxmatch()
{
int res = 0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(bfs())
{
memset(used,0,sizeof(used));
for(int i=1;i<=n;i++)
res += (cx[i] == -1 && dfs(i));
}
return res;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
return 0;
}
Read More ~
