Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 二分图匹配，匈牙利算法~尝试用bfs搜为什么过不去？

Posted by celia01 at 2012-04-06 12:46:04 on Problem 2446

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int xmax = 600, ymax = 600;
int xN, yN;
bool g[xmax][ymax];
int xM[xmax],yM[ymax];
bool chky[ymax];
int Q[1300], prev[xmax];

int MaxMatch() {
int res = 0;
int qs, qe;
memset(xM, -1, sizeof(xM));
memset(yM, -1, sizeof(yM));
memset(chky, -1, sizeof(chky));
for (int i = 0; i < xN; i++){
if (xM[i] == -1){
qs = qe = 0;
Q[qe++] = i;
prev[i] = -1;
bool flag = 0;
while (qs < qe && !flag){
int u = Q[qs];
for (int v = 0; v < yN && !flag; v++){
if (g[u][v] && chky[v] != i) {
chky[v] = i; Q[qe++] = yM[v];
if (yM[v] >= 0)
prev[yM[v]] = u;
else {
flag = 1;
int d = u, e = v;
while (d != -1) {
int t = xM[d];
xM[d] = e; yM[e] = d;
d = prev[d]; e = t;
}
}
}
qs++;
}
}
if (xM[i] != -1) res++;
}
}
return res;
}

bool map[40][40];
int idd[40][40];
int main(){
int i, j, p, q;
int n, m, k, x, y;
while(~scanf("%d%d%d",&m,&n,&k)){
memset(g,0,sizeof(g));
if((m*n-k)&1){
cout<<"NO"<<endl;
continue;
}
memset(map,true,sizeof(map));
for(i=0;i<k;i++){
scanf("%d%d",&y,&x);
map[x-1][y-1] = false;
}
p = q = 0;
for(i=0;i<m;i++){
for(j=0;j<n;j++){
if(map[i][j]){
if((i+j)&1)
idd[i][j] = p++;
else
idd[i][j] = q++;
}
}
}
for(i=0;i<m;i++){
for(j=0;j<n;j++){
if(map[i][j]){
if((i+j)&1){
if(i-1>=0&&map[i-1][j])
g[idd[i][j]][idd[i-1][j]] = 1;
if(j-1>=0&&map[i][j-1])
g[idd[i][j]][idd[i][j-1]] = 1;
if(i+1<m&&map[i+1][j])
g[idd[i][j]][idd[i+1][j]] = 1;
if(j+1<n&&map[i][j+1])
g[idd[i][j]][idd[i][j+1]] = 1;
}
}
}
}
xN = p; yN=q;
if(MaxMatch()==(m*n-k)/2){
cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
}
return 0;
}

Followed by: