题目链接： ， 匈牙利算法裸题。
刚刚学的二分匹配，还是要多刷题。
这道题可以直接套模板，我是根据题目上面的来做的，所以就先加了个染色优化，效果一般吧。
#include#include #include #include #include #include #include #include using namespace std;#define LL __int64#define eps 1e-8#define INF 1e8#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int MOD = 2333333; const int maxn = 1000 + 5;vector e[maxn];int color[maxn] , match[maxn] , vis[maxn];void DFS(int s) { for(int i = 0 ; i < e[s].size() ; i++) { int j = e[s][i]; if(!color[j]) { color[j] = 3 - color[s]; DFS(j); } }}bool find(int v){ if(vis[v]) return false; vis[v] = 1; for(int i = 0 ; i < e[v].size() ; i++) { int u = e[v][i]; if(!vis[u]) { vis[u] = 1; if(!match[u] || find(match[u])) { match[u] = v; return true; } } } return false;}int main(){ int n , m , u , v , res = 0; scanf("%d %d" , &n , &m); memset(color , 0 , sizeof(color)); memset(match , 0 , sizeof(match)); while(m--) { scanf("%d %d" , &u , &v); e[u].push_back(v); e[v].push_back(u); } for(int i = 1 ; i <= n ; i++) { if(!color[i]) { color[i] = 1; DFS(i); } } for(int i = 1 ; i <= n ; i++) { if(color[i] == 1) { memset(vis , 0 , sizeof(vis)); res += find(i); } } printf("%d\n" , res);}