做过的二分图匹配题目汇总【不断更新】
1.
Hdu4619:http://acm.hdu.edu.cn/showproblem.php?pid=4619
某次多校的题目。
最大独立集 = 顶点数 - 最大匹配数
可以确定每两个合为一体的话可以看作一二分图。 然后这个最大独立集。
2.
POJ1422：http://poj.org/problem?id=1422
有向无环图化为二分图。 拆点连边。
求最小路径覆盖。 亦 = 顶点数 - 最大匹配数。
3.
POJ3020：http://poj.org/problem?id=3020
反证法可证图为二分图。 二分图好构建。 划分关系不明确。 比如对于X,Y不确定X,Y分别属于哪部半图。
最小路径覆盖。
现在可以明白最小路径覆盖针对有向图以及二分图的路径关系 = 顶点数 - 最大匹配数呗~ 这地方的理解结合非路径终点理解就很容易了
自己写的时候循环弄错。
for(i<=sum) 其实照自己的构图方式应该是 for(i<=n*m)
附个代码：
#include <iostream>#include <cstring>#include <cstdio>using namespace std;#define clr(x,y) memset(x,y,sizeof(x))const int maxn = 500; //二分图左、右两边数目int n, m, sum;int match[maxn], g[maxn][maxn], adj[maxn][maxn];bool used[maxn];bool find(int u){ for(int i = 1; i <= n*m; i++) { if(g[u][i] && !used[i]) { used[i] = true; if(match[i] == -1 || find(match[i])) { match[i] = u; return true; } } } return false;}int hungary(){ int cnt = 0; clr(match, -1); for(int i = 1; i <= n*m; i++) { clr(used, 0); if(find(i)) cnt++; } return cnt;}int main(){ char c; int ncase; scanf("%d", &ncase); while(ncase--) { scanf("%d %d",&n, &m); { sum = 0; clr(adj, 0); clr(g, 0); scanf("%^c"); //孤陋寡闻了 scanf("%c")原来也是读缓冲区的 for(int i = 1;i <= n;i++) { for(int j = 1; j <= m; j++) { scanf("%c", &c); if(c == '*') { adj[i][j] = 1; sum++; } } getchar(); } for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) { int x = (i-1)*m + j; if(adj[i][j]) { if(adj[i-1][j]) g[x][x-m] = 1; if(adj[i+1][j]) g[x][x+m] = 1; if(adj[i][j-1]) g[x][x-1] = 1; if(adj[i][j+1]) g[x][x+1] = 1; } } // printf("~%d %d\n",sum,hungary()); printf("%d\n",sum - hungary()/2); } } return 0;}