//poj_2446
/*==================================================*\
| 二分圖匹配(匈牙利算法DFS 實現(xiàn))
| INIT: g[][]鄰接矩陣;
| 優(yōu)點:實現(xiàn)簡潔容易理解坎弯,適用于稠密圖,DFS找增廣路快。
| 找一條增廣路的復(fù)雜度為O(E),最多找V條增廣路瘟裸,故時間復(fù)雜度為O(VE)
==================================================*/
#include<stdio.h>
#include<memory.h>
#define MAX 1089 //33*33
bool g[MAX][MAX]; //鄰接矩陣蛮瞄,true代表有邊相連
bool flag,visit[MAX]; //記錄V2中的某個點是否被搜索過
int match[MAX]; //記錄與V2中的點匹配的點的編號
int cnt; //二分圖中左邊棍郎、右邊集合中頂點的數(shù)目
bool hole[MAX][MAX];
int id[MAX][MAX];
// 匈牙利算法
bool dfs(int u)
{
for (int i = 1; i <= cnt; ++i)
{
if (g[u][i] && !visit[i]) //如果節(jié)點i與u相鄰并且未被查找過
{
visit[i] = true; //標(biāo)記i為已查找過
if (match[i] == -1 || dfs(match[i])) //如果i未在前一個匹配M中钦讳,或者i在匹配M中阅签,但是從與i相鄰的節(jié)點出發(fā)可以有增廣路徑
{
match[i] = u; //記錄查找成功記錄掐暮,更新匹配M(即“取反”)
return true; //返回查找成功
}
}
}
return false;
}
int MaxMatch()
{
int i,sum=0;
memset(match,-1,sizeof(match));
for(i = 1 ; i <= cnt ; ++i)
{
memset(visit,false,sizeof(visit)); //清空上次搜索時的標(biāo)記
if( dfs(i) ) //從節(jié)點i嘗試擴展
{
sum++;
}
}
return sum;
}
int main(void)
{
int i,j,k,m,n,ans,y,x;
while (scanf("%d %d %d",&m,&n,&k)!=EOF)
{
memset(g,false,sizeof(g));
memset(hole,false,sizeof(hole));
for (i = 1; i <= k; ++i)
{
scanf("%d %d",&y,&x);
hole[x][y] = true;
}
if((m*n-k)&1) //奇偶剪枝
{
puts("NO");
continue;
}
cnt = 0;
for (i = 1; i <= m; ++i)
{
for (j = 1; j <= n; ++j)
{
if(hole[i][j] == false) //對沒有涂黑的點進行標(biāo)號
{
id[i][j] = ++cnt;
}
}
}
for (i = 1; i <= m; ++i)
{
for (j = 1; j <= n; ++j)
{
if(hole[i][j] == false)
{
if(i-1>0 && hole[i-1][j] == false) //建圖。政钟。要注意邊界問題
g[ id[i][j] ][ id[i-1][j] ] = true;
if(i+1<=m && hole[i+1][j] == false)
g[ id[i][j] ][ id[i+1][j] ] = true;
if(j-1>0 && hole[i][j-1] == false)
g[ id[i][j] ][ id[i][j-1] ] = true;
if(j+1<=n && hole[i][j+1] == false)
g[ id[i][j] ][ id[i][j+1] ] = true;
}
}
}
ans = MaxMatch();
if (ans == cnt)
puts("YES");
else
puts("NO");
}
return 0;
}
增廣路算法 模板
最后編輯于 :
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門廉嚼,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人倒戏,你說我怎么就攤上這事怠噪。” “怎么了杜跷?”我有些...
- 文/不壞的土叔 我叫張陵舰绘,是天一觀的道長。 經(jīng)常有香客問我葱椭,道長捂寿,這世上最難降的妖魔是什么? 我笑而不...
- 正文 為了忘掉前任孵运,我火速辦了婚禮秦陋,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘治笨。我一直安慰自己驳概,他們只是感情好,可當(dāng)我...
- 文/花漫 我一把揭開白布旷赖。 她就那樣靜靜地躺著顺又,像睡著了一般。 火紅的嫁衣襯著肌膚如雪等孵。 梳的紋絲不亂的頭發(fā)上稚照,一...
- 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼返弹!你這毒婦竟也來了锈玉?” 一聲冷哼從身側(cè)響起,我...
- 正文 年R本政府宣布源哩,位于F島的核電站,受9級特大地震影響鸦做,放射性物質(zhì)發(fā)生泄漏励烦。R本人自食惡果不足惜,卻給世界環(huán)境...
- 文/蒙蒙 一泼诱、第九天 我趴在偏房一處隱蔽的房頂上張望坛掠。 院中可真熱鬧,春花似錦治筒、人聲如沸屉栓。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽友多。三九已至,卻和暖如春堤框,著一層夾襖步出監(jiān)牢的瞬間域滥,已是汗流浹背纵柿。 一陣腳步聲響...