HDOJ 1151 二分匹配

本文主要是介绍HDOJ 1151 二分匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我的AC代码

#include <iostream>
#include <string.h>
using namespace std;
int n,m,k,t,s,e,result;
int map[130][130],v[130],link[130];
void init(){scanf("%d", &n);scanf("%d", &m);memset(map, 0, sizeof(map));memset(link, -1, sizeof(link));result = 0;for(int i = 0; i < m; i++){scanf("%d %d", &s, &e);map[s][e] = 1;}
}
bool find (int x){for(int i = 1; i <= n; i++){if(!v[i] && map[x][i]){v[i] = 1;if(link[i]==-1 || find(link[i])){link[i] = x;return true;}}}return false;
}
int main(int argc, const char * argv[])
{while (scanf("%d", &t)!=EOF) {while (t>0) {init();for(int i = 1; i <= n; i++){memset(v, 0, sizeof(v));if(find(i)) result++;}printf("%d\n", n-result);t--;}}
}

思路见这篇博客

这篇关于HDOJ 1151 二分匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---