首页 > 代码库 > hdu--5093--经典二分图的行列匹配
hdu--5093--经典二分图的行列匹配
感觉图论的题 都是难在 如何建图上 本题也是如此
我们主要是将行与列 分开来考虑 每一座冰山隔开的海水 都可以看成一个“块” 在这上面是可以放船的 然后是将这连续的海水可能中间会有冰 但不影响看成一个块
列 也是同样处理的 然后 每一个 列与行的交点的海水 不就是说明这个行与列是矛盾的 只能存在一个 就将它们连边. 最后就是去求 二分图的 最大匹配
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 int cntX , cntY , n , m; 6 const int size = 55; 7 char mp[size][size]; 8 int x[size][size]; 9 int y[size][size]; 10 bool vis[size*size]; 11 int linker[size*size]; 12 bool edge[size*size][size*size]; 13 14 void init( ) 15 { 16 cntX = cntY = 1; 17 memset( x , 0 , sizeof(x) ); 18 memset( y , 0 , sizeof(y) ); 19 memset( edge , false , sizeof(edge) ); 20 memset( linker , 0 , sizeof(linker) ); 21 } 22 23 void solveX( ) 24 { 25 for( int i = 1 ; i<=n ; i++ ) 26 { 27 int j = 1; 28 while( j<=m ) 29 { 30 if( mp[i][j]==‘*‘ ) 31 { 32 x[i][j] = cntX; 33 ++ j; 34 while( j<=m ) 35 { 36 if( mp[i][j]==‘*‘ ) 37 { 38 x[i][j] = cntX; 39 ++ j; 40 } 41 else if( mp[i][j]==‘o‘ ) 42 { 43 ++ j; 44 continue; 45 } 46 else 47 { 48 break; 49 } 50 } 51 ++ cntX; 52 } 53 else 54 { 55 ++ j; 56 } 57 } 58 } 59 } 60 61 void solveY( ) 62 { 63 for( int i = 1 ; i<=m ; i++ )//列 64 { 65 int j = 1; 66 while( j<=n )//行 67 { 68 if( mp[j][i]==‘*‘ ) 69 { 70 y[j][i] = cntY; 71 edge[ x[j][i] ][ y[j][i] ] = true; 72 ++ j; 73 while( j<=n ) 74 { 75 if( mp[j][i]==‘*‘ ) 76 { 77 y[j][i] = cntY; 78 edge[ x[j][i] ][ y[j][i] ] = true; 79 ++ j; 80 } 81 else if( mp[j][i]==‘o‘ ) 82 { 83 ++ j; 84 continue; 85 } 86 else 87 { 88 break; 89 } 90 } 91 ++ cntY; 92 } 93 else 94 { 95 ++ j; 96 } 97 } 98 } 99 }100 101 bool dfs( int u )102 {103 for( int v = 1 ; v<cntY ; v++ )104 {105 if( edge[u][v] && !vis[v] )106 {107 vis[v] = true;108 if( !linker[v] || dfs( linker[v] ) )109 {110 linker[v] = u;111 return true;112 }113 }114 }115 return false;116 }117 118 int solve( )119 {120 int ans = 0;121 for( int i = 1 ; i<cntX ; i++ )122 {123 memset( vis , false , sizeof(vis) );124 if( dfs(i) )125 ++ ans;126 } 127 return ans;128 }129 130 int main()131 {132 cin.sync_with_stdio(false);133 int t , ans;134 while( cin >> t )135 {136 while( t-- )137 {138 init( );139 cin >> n >> m;140 for( int i = 1 ; i<=n ; i++ )141 {142 cin >> (mp[i]+1);143 }144 solveX( );145 solveY( );146 /*147 for( int i = 1 ; i<=n ; i++ )148 {149 for( int j = 1 ; j<=m ; j++ )150 {151 cout << x[i][j] << " ";152 }153 cout << endl;154 }155 for( int i = 1 ; i<=m ; i++ )156 {157 for( int j = 1 ; j<=n ; j++ )158 {159 cout << y[i][j] << " ";160 }161 cout << endl;162 }163 */164 ans = solve( );165 cout << ans << endl;166 }167 }168 return 0;169 }
hdu--5093--经典二分图的行列匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。