首页 > 代码库 > 二分图最大匹配题目汇总 POJ 1274、2239、3020、3715
二分图最大匹配题目汇总 POJ 1274、2239、3020、3715
POJ 1274
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
using namespace std;
vector<int> aa[205];
int flag[205],visted[205];
bool dfs(int x){
for(int i=0;i<aa[x].size();++i){
if(!visted[aa[x][i]]){
visted[aa[x][i]]=1;
if(!flag[aa[x][i]]||dfs(flag[aa[x][i]])){
flag[aa[x][i]]=x;
return true;
}
}
}
return false;
}
int main(){
int n,m;
while(~scanf("%d %d",&n,&m)){
memset(aa,0,sizeof(aa));
memset(flag,0,sizeof(flag));
int num,x;
for(int i=1;i<=n;++i){
scanf("%d",&num);
while(num--){
scanf("%d",&x);
aa[i].push_back(x);
}
}
int sum=0;
for(int i=1;i<=n;++i){
memset(visted,0,sizeof(visted));
if(dfs(i))
sum++;
}
printf("%d\n",sum);
}
return 0;
}
POJ 2239
#include <iostream>
#include <vector>
#include <string.h>
#include <cstdio>
using namespace std;
vector<int> ss[305];
int flag[102],visit[102];
bool dfs(int x){
for(int i=0;i<ss[x].size();++i){
if(!visit[ss[x][i]]){
visit[ss[x][i]]=1;
if(!flag[ss[x][i]]||dfs(flag[ss[x][i]])){
//printf("x=%d i=%d flag=%d\n",x,i,flag[ss[x][i]]);
flag[ss[x][i]]=x;
return true;
}
}
}
return false;
}
int main(){
int n;
while(~scanf("%d",&n)){
int num,x,y;
memset(ss,0,sizeof(ss));
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;++i){
scanf("%d",&num);
while(num--){
scanf("%d %d",&x,&y);//day class
int xx=(x-1)*12+y;
ss[i].push_back(xx);
}
}
int sum=0;
for(int i=1;i<=n;++i){
memset(visit,0,sizeof(visit));
if(dfs(i))
sum++;
}
printf("%d\n",sum);
}
return 0;
}
POJ 3020
法一：
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>map[400];//按奇偶性建二分图
int t,n,m;
int match[400],fy[400],ln,rn;
int map1[41][11];//原始图
int dirt[4][2]={0,1,0,-1,1,0,-1,0};
int path(int u)
{
for(int i=0,j;i<map[u].size();i++)
{
j=map[u][i];
if(!fy[j])
{
fy[j]=1;
if(match[j]==-1||path(match[j]))
{
match[j]=u;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,x,y,ans;
char tmp;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
ln=rn=0;
for(i=1;i<=n;i++)
{
getchar();
for(j=1;j<=m;j++)
{
scanf("%c",&tmp);
if(tmp=='*')
{
if((i+j)&1)//奇点
map1[i][j]=++ln;
else//偶点
map1[i][j]=++rn;
}
else
map1[i][j]=0;
}
}
for(i=1;i<=ln;i++)
map[i].clear();
for(i=1;i<=rn;i++)
match[i]=-1;
//建二分图
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(!map1[i][j]||!((i+j)&1))
continue;
for(int k=0;k<4;k++)
{
x=i+dirt[k][0];
y=j+dirt[k][1];
if(x<=0||x>n||y<=0||y>m||!map1[x][y])
continue;
map[map1[i][j]].push_back(map1[x][y]);
}
}
//求最大匹配 最小点覆盖
ans=0;
for(i=1;i<=ln;i++)
{
for(j=1;j<=rn;j++)
fy[j]=0;
if(path(i))
ans++;
}
printf("%d\n",ln+rn-ans);
}
return 0;
}
法二：
#include <iostream>
#include <cstring>
#include <cstdio>
// 最大独立集
//思路是出现*的坐标标为true，然后一每个为true的坐标为起点
//用匈利亚算法确定是否有增广路存在。注意，
//这样统计出来的数据是最大二分匹配的二倍，因为默认的看成了无向图。
//result = 为true的结点数 - 最大二分匹配
using namespace std;
const int N = 50;
bool g[N][N];
bool usd[N][N];
int lx[N][N], ly[N][N];
int h, w;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool can(int x, int y) {
int a, b, i;
for(i = 0; i < 4; ++i) {
a = x + dir[i][0];
b = y + dir[i][1];
if(!usd[a][b] && g[a][b]) {
usd[a][b] = true;
if((lx[a][b] == -1 && ly[a][b] == -1) || can(lx[a][b], ly[a][b])) {
lx[a][b] = x;
ly[a][b] = y;
return true;
}
}
}
return false;
}
int main() {
//freopen("data.in", "r", stdin);
int i, j, t;
int n, cnt;
char c;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &h, &w);
getchar();
memset(g, false, sizeof(g));
for(n = 0, i = 1; i <= h; ++i) {
for(j = 1; j <= w; ++j) {
scanf("%c", &c);
//printf("%c", c);
if(c == '*') {g[i][j] = true; n++;}
// printf("%d", g[i][j]);
}
getchar();
// cout << endl;
}
cnt = 0;
memset(lx, -1, sizeof(lx));
memset(ly, -1, sizeof(ly));
for(i = 1; i <= h; ++i) {
for(j = 1; j <= w; ++j) {
if(g[i][j]) {
memset(usd, 0, sizeof(usd));
if(can(i, j)) cnt++;
}
}
}
printf("%d\n", n - cnt/2);
}
return 0;
}
法三：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int w,h;
char scenario[45][15];
int num[45][15];
int map[410][410];
bool isvisted[410];
int match[410];
int n;
bool path(int u)
{
for (int i = 1; i <= n; ++ i)
{
if (map[u][i] && !isvisted[i])
{
isvisted[i] = true;
if (match[i] == -1 || path(match[i]))
{
match[i] = u;
return true;
}
}
}
return false;
}
void buildMap()
{
memset(map, 0, sizeof(map));
memset(num, 0, sizeof(num));
n = 0;
for (int i = 1; i <= h; ++ i)
{
for (int j = 1; j <= w; ++ j)
{
if (scenario[i][j] == '*')
{
num[i][j] = ++n;
}
}
}
for (int i = 1; i <= h; ++ i)
{
for (int j = 1; j <= w; ++ j)
{
if (num[i][j] > 0)
{
if (num[i - 1][j] > 0)
{
map[num[i][j]][num[i - 1][j]] = 1;
}
if (num[i + 1][j] > 0)
{
map[num[i][j]][num[i + 1][j]] = 1;
}
if (num[i][j - 1] > 0)
{
map[num[i][j]][num[i][j - 1]] = 1;
}
if (num[i][j + 1] > 0)
{
map[num[i][j]][num[i][j + 1]] = 1;
}
//num[i][j] = 0;
}
}
}
}
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
int count = 0;
scanf("%d %d", &h, &w);
memset(scenario, 0, sizeof(scenario));
memset(match, -1, sizeof(match));
for (int i = 1; i <= h; ++ i)
{
scanf("%s", &scenario[i][1]);
}
buildMap();
for (int i = 1; i <= n; ++ i )
{
memset(isvisted, false, sizeof(isvisted));
if (path(i))
{
++count;
}
}
printf("%d\n", n - count/2);
}
return 0;
}
POJ 3715
#include <iostream>//poj3715 博客里面有说明
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 250
int n,m;
int g[maxn][maxn];
int a[maxn];
int fugai[maxn],visit[maxn],prex[maxn],prey[maxn];
void init()
{
memset(g,0,sizeof(g));
memset(a,0,sizeof(a));
memset(prex,-1,sizeof(prex));
memset(prey,-1,sizeof(prey));
memset(fugai,0,sizeof(fugai));
}
int canx(int x)
{
if(fugai[x]==1) return 0;
int i,j;
for(i=0; i<n; i++)
if(g[x][i] && visit[i]==0 && fugai[i]==0)
{
visit[i]=1;
if(prey[i]==-1 || canx(prey[i]))
{
prex[x]=i;
prey[i]=x;
return 1;
}
}
return 0;
}
int cany(int y)
{
if(fugai[y]==1) return 0;
int i,j;
for(i=0; i<n; i++)
if(g[y][i] && visit[i]==0 && fugai[i]==0)
{
visit[i]=1;
if(prex[i]==-1 || cany(prex[i]))
{
prey[y]=i;
prex[i]=y;
return 1;
}
}
return 0;
}
void solve()
{
int i,j,res=0;
for(i=0; i<n; i++)
if(a[i]==0) //匈牙利之用从二分图的一边，搜索
{
memset(visit,0,sizeof(visit));
res+=canx(i);
}
printf("%d",res);
int x,y;
for(i=0; i<n; i++)
{
if(a[i]==0)//覆盖集中的点可以是x的点也可以是y的点
{
if(prex[i]==-1)continue;//如果不是原来已经匹配的边
y=prex[i];//从原来和他匹配的边找增广路
prex[i]=-1;
prey[y]=-1;
fugai[i]=1;
memset(visit,0,sizeof(visit));
if(cany(y)==1)//如果找到增广路那么，这个点就不是覆盖集中的点
{
fugai[i]=0;
//prex[i]=y;
//prey[y]=i;
}
else
printf(" %d",i);
}
else
{
if(prey[i]==-1) continue;
x=prey[i];
prey[i]=-1;
prex[x]=-1;
fugai[i]=-1;
memset(visit,0,sizeof(visit));
if(canx(x)==1)
{
fugai[i]=0;
//prey[i]=x;
//prex[x]=i;
}
else
printf(" %d",i);
}
}
puts("");
}
int main()
{
int t,i,j,k;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n,&m);
init();
int x,y;
for(i=0; i<n; i++)
{
scanf("%d", &x);
a[i]=x;
}
for(i=0; i<m;i++)
{
scanf("%d%d", &x,&y);
if(a[x]!=a[y])
{
if(a[x]==1) swap(x,y);
g[x][y]=1;//建图
g[y][x]=1;
}
}
solve();
}
}
二分图最大匹配题目汇总 POJ 1274、2239、3020、3715
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。