匈牙利模板C++

#include<iostream> #include<cstring> #define MAX 1000 using namespace std; int vis[MAX],match[MAX]; int head[MAX]; int cnt = 0,n; struct node { int to,next; }edge[MAX*MAX]; void addedge(int from,int to) { edge[cnt] = {to,head[from]}; //链式向量星 head[from] = cnt++; } int getit(int now) { for(int i = head[now];~i;i=edge[i].next) { int to = edge[i].to; if(vis[to]) continue; //如果这个点已经被占了则跳过 vis[to] = 1; //没有则占据并记录 if(match[to] == 0 || getit(match[to])) //match[to]存放几号出发点； 如果为0说明该点没有被其他点给占用直接进入 否则递归腾点 { match[to] = now; return 1; } } return 0; } void getans() { int ans = 0; for(int i = 1 ; i <= n ; i++ ) { memset(vis,0,sizeof(vis)); //每次都要初始化 if(getit(i)) ans++; ///如果返回值为1ans++ } cout<<ans<<endl; } int main() { int m,a,b; memset(head,-1,sizeof(head)); cin>>n>>m; ///点数 边数 for(int i = 0 ; i < m ; i++) { cin>>a>>b; addedge(a,b); //构图 } getans(); return 0; }