周大爷在比赛中搜到的黑科技二分图模版，复杂度为m√(n)：
注意：点的序号要从0开始！
需要把nx，ny都赋值为n(点数)
const int MAXN = ;
const int MAXM = *; struct Edge {
int v;
int next;
} edge[MAXM]; struct node {
double x, y;
double v;
} a[MAXN], b[MAXN]; int nx, ny;
int cnt;
int t;
int dis; int first[MAXN];
int xlink[MAXN], ylink[MAXN];
/*xlink[i]表示左集合顶点所匹配的右集合顶点序号，ylink[i]表示右集合i顶点匹配到的左集合顶点序号。*/
int dx[MAXN], dy[MAXN];
/*dx[i]表示左集合i顶点的距离编号，dy[i]表示右集合i顶点的距离编号*/
int vis[MAXN]; //寻找增广路的标记数组 void init() {
cnt = ;
memset(first, -, sizeof(first));
memset(xlink, -, sizeof(xlink));
memset(ylink, -, sizeof(ylink));
} void read_graph(int u, int v) {
edge[cnt].v = v;
edge[cnt].next = first[u], first[u] = cnt++;
} int bfs() {
queue<int> q;
dis = INF;
memset(dx, -, sizeof(dx));
memset(dy, -, sizeof(dy));
for(int i = ; i < nx; i++) {
if(xlink[i] == -) {
q.push(i);
dx[i] = ;
}
}
while(!q.empty()) {
int u = q.front();
q.pop();
if(dx[u] > dis) break;
for(int e = first[u]; e != -; e = edge[e].next) {
int v = edge[e].v;
if(dy[v] == -) {
dy[v] = dx[u] + ;
if(ylink[v] == -) dis = dy[v];
else {
dx[ylink[v]] = dy[v]+;
q.push(ylink[v]);
}
}
}
}
return dis != INF;
} int find(int u) {
for(int e = first[u]; e != -; e = edge[e].next) {
int v = edge[e].v;
if(!vis[v] && dy[v] == dx[u]+) {
vis[v] = ;
if(ylink[v] != - && dy[v] == dis) continue;
if(ylink[v] == - || find(ylink[v])) {
xlink[u] = v, ylink[v] = u;
return ;
}
}
}
return ;
} int MaxMatch() {
int ans = ;
while(bfs()) {
memset(vis, , sizeof(vis));
for(int i = ; i < nx; i++) if(xlink[i] == -) {
ans += find(i);
}
}
return ans;
} double dist(const node a, const node b) {
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
调用：
init();
for(int i = ; i < m; i++) {
if(l[edgee[i][]] && edgee[i][] != s && !l[edgee[i][]]) read_graph(edgee[i][],edgee[i][]);
if(l[edgee[i][]] && edgee[i][] != s && !l[edgee[i][]]) read_graph(edgee[i][],edgee[i][]);
}
nx = n;
ny = n;
int ans = MaxMatch();