<ins id="pjuwb"></ins>

<blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

<noscript id="pjuwb"></noscript>

<sup id="pjuwb"><pre id="pjuwb"></pre></sup>

<dd id="pjuwb"></dd>

<abbr id="pjuwb"></abbr>

gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

Pku 2226--Muddy Fields

二分圖匹配，關鍵：建圖

#include <stdio.h>

#include <memory.h>

const int max = 1001 ;

bool use[max] , map[max][max] ;

int link[max] ;

int LNum , RNum ;

const int MaxSize = 51 ;

char cTemp[MaxSize][MaxSize] ;

//建圖

void Build(int r, int c)

{

int i , j , k ;

LNum = 0 ;

RNum = 0 ;

int LeftMem[MaxSize][MaxSize] ;

memset( LeftMem, 0xff, sizeof(LeftMem) ) ;

memset( map, 0, sizeof(map) ) ;

memset( link, 0xff, sizeof(link) ) ;

for ( i = 0 ; i < r ; i++ )

for ( j = 0 ; j < c ; j++ )

{

if ( cTemp[i][j] == '*' )

{

LeftMem[i][j] = LNum ;

for ( k = j + 1 ; k < c ; k++ )

{

//每一列連續的 * 記為同一個值

if ( cTemp[i][k] == '*' )

{

LeftMem[i][k] = LNum ;

}

else {

j = k - 1 ;

break ;

}

}

if ( k >= c )

{

k = 0 ;

j = c ;

}

LNum++ ;

}

}

for ( i = 0 ; i < c ; i++ )

{

for ( j = 0 ; j < r ; j++ )

{

if ( cTemp[j][i] == '*' )

{

//行跟列有'*'交叉，則匹配

map[LeftMem[j][i]][RNum] = true ;

for ( k = j + 1 ; k < r ; k++ )

{

if ( cTemp[k][i] != '*' )

{

j = k - 1 ;

break ;

}

else {

map[LeftMem[k][i]][RNum] = true ;

}

}

if ( k >= r )

{

k = 0 ;

j = r ;

}

RNum++ ;

}

}

}

}

bool FindPath( int u )

{

int v ;

for ( v = 0 ; v < RNum ; v++ )

{

if ( !use[v] && map[u][v] )

{

use[v] = true ;

if ( link[v] == -1 || FindPath( link[v] ) )

{

link[v] = u ;

return true ;

}

}

}

return false ;

}

void Init( void )

{

int R , C ;

int i ;

scanf("%d %d", &R, &C) ;

for ( i = 0 ; i < R ; i++ )

{

scanf("%s", &cTemp[i]) ;

}

Build( R, C ) ;

int ans = 0 ;

for ( i = 0 ; i < LNum ; i++ )

{

memset( use, 0, sizeof(use) );

if ( FindPath(i) )

ans++ ;

}

printf("%d\n", ans) ;

}

int main()

{

Init() ;

return 0 ;

}

posted on 2008-10-31 21:29 巫閱讀(425) 評論(0) 編輯收藏引用所屬分類: 圖論

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: POJ 3662--Telephone Lines(二分枚舉 + Dij) POJ 3268(最短路徑 SPFA) POJ 1511(SPFA) POJ 1511(Dij + Heap) POJ 1094(簡單的拓撲排序) Pku 2226--Muddy Fields Pku 3678--Katu Puzzle

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

精品久久久久香蕉网| 久久99热只有频精品8| 狠色狠色狠狠色综合久久| 亚洲中文久久精品无码| 久久国产劲爆AV内射—百度| 久久人妻少妇嫩草AV无码专区| 久久人妻AV中文字幕| 国产欧美久久久精品影院| 亚洲七七久久精品中文国产 | 日韩精品久久久肉伦网站 | 久久99久久无码毛片一区二区| a级毛片无码兔费真人久久| 国产精品永久久久久久久久久| 精品久久久无码中文字幕| 久久国产热这里只有精品| 色老头网站久久网| 亚洲精品乱码久久久久久蜜桃不卡| 伊人久久综合无码成人网| 久久精品国产亚洲AV无码偷窥| 国产精品久久久久影院色| 国产精品成人99久久久久| 亚洲人AV永久一区二区三区久久 | 久久久久亚洲av毛片大| 久久人人青草97香蕉| 狠狠色噜噜狠狠狠狠狠色综合久久| AAA级久久久精品无码区| 午夜精品久久久久久久无码| 亚洲综合熟女久久久30p| 99久久www免费人成精品| 久久天天躁狠狠躁夜夜不卡 | 亚洲精品国产字幕久久不卡| 色综合久久88色综合天天 | 久久久精品人妻一区二区三区四| 久久国产高清字幕中文| 人妻无码αv中文字幕久久琪琪布人妻无码精品久久亚瑟影视 | 久久香蕉综合色一综合色88| 亚洲欧美国产日韩综合久久| 99久久精品国内| 久久强奷乱码老熟女网站| 久久精品国产99久久香蕉| 精品熟女少妇a∨免费久久|