首页 > 代码库 > HDU 1068 Girls And Boys 二分图题解
HDU 1068 Girls And Boys 二分图题解
选择出一组学生,这组学生里面不能彼此之间有过恋爱史的。
又是一个典型的二分图问题。
不过需要把所有学生看成一组*2,然后求最大匹配,然后除以2. 这样其实建图的时候,建成有向图也是可以的了。而且也是给出了两个方向的点了。
注意本题没有给出最大数是多少学生了,所以最好使用动态分配内存了。
而且本题的输入处理也特别点,要处理好,用好scanf这个函数。
#include <stdio.h> #include <stdlib.h> bool **stus, *used; int *linker; int N; void initGraph() { stus = (bool **) malloc(N * sizeof(bool *)); for (int i = 1; i < N; i++) stus[i] = (bool *) calloc(N, sizeof(bool)); } void freeGraph() { for (int i = 1; i < N; i++) free(stus[i]); free(stus); } bool hunDFS(int u) { for (int v = 1; v < N; v++) { if (!used[v] && stus[u][v]) { used[v] = true; if (!linker[v] || hunDFS(linker[v])) { linker[v] = u; return true; } } } return false; } int hungary() { int ans = 0; linker = (int *) calloc(N, sizeof(int)); for (int i = 1; i < N; i++) { used = (bool *) calloc(N, sizeof(bool)); if (hunDFS(i)) ans++; free(used); } free(linker); return ans>>1; } int main() { int k, v; while (scanf("%d", &N) != EOF) { N++; initGraph(); for (int u = 1; u < N; u++) { scanf("%d: (%d)", &v, &k); for (int i = 0; i < k; i++) { scanf("%d", &v); stus[u][v+1] = stus[v+1][u] = true; } } printf("%d\n", N - 1 - hungary()); freeGraph(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。