详谈二分图最大匹配解法 和 网络流 Dinic解法
1.题目分析
2.匈牙利二分图匹配解法
3.Dinic网络流解法
1.题目分析
由题意得，我们可以对任意两行或两列进行交换操作。初看似乎没有头绪，那先来分析一组简单数据。
1
0 0 1
1 0 0
0 1 0
我们考虑将每一行的行数与该行黑色方块所在的列数连一条边。
然后可以将它进行如下图的变化得到答案
我们可以看出，右图中的每一行列都至少有一个符合的匹配（显然）。
进而我们思考，是否是每一行列至少存在一组合法匹配的图形合法呢？
答案是的
因为任意两行或者任意两列之间的交换都不会破坏他们的平衡性。
也就是说，任意2个黑色方块，如果它们初始状态时不在同一行（列），那么无论如何交换，它们都不会在同一行（列）。
所以我们可以得到第一种解法 匈牙利二分图匹配解法。
2.匈牙利二分图匹配解法
经过上述分析，交换操作并不会影响图的最大匹配，我们只需判断每一行是否都可以合法匹配即可。
那么显然是一道板子似的二分图最大匹配。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 400 + 15 ;//稍微开大一点。
int head[ N*N ] , to [ N*N ] , next[ N*N ] , tot = 1 ,ans = 0 ;
int match[ N ] , visit[ N ] , n , T ;
inline int read() //快读
{
int s = 0,w = 1;
char g = getchar();
while(g<'0'||g>'9'){if(g=='-')w*=-1;g = getchar();}
while(g>='0'&&g<='9'){s = s*10+g-'0';g = getchar();}
return s*w;
}
void add( int x , int y ){ //前向星建边
tot++ ;
to[ tot ] = y ;
next[ tot ] = head[ x ] ;
head[ x ] = tot ;
}
bool dfs( int x ){ //匹配
for( int i = head[ x ] , y ; i ; i = next[ i ] )
if( !visit[ y = to[ i ] ] ){
visit[ y ] = 1 ;
if( !match[ y ] || dfs(match[ y ] ) ){
match[ y ] = x ; return true ;
}
}
return false ;
}
void clear(){ //多组数据，清零初始化
T-- ;
ans = 0 ;
for( int i = 1 ; i<= tot ; i++ ) //这种方式可以避免memset()浪费过多时间
to[ i ] = head[ i ] = next[ i ] = 0 ;
tot = 1 ;
for( int i = 1 ; i <= 2*n ; i++ ){
match[ i ] = 0 ;
}
}
int main()
{
T = read() ;
while( T != 0 ){
n = read() ;
for( int i = 1 ; i <= n ; i++)
for( int j = 1 ; j <= n ; j++ ){//读入并建边
int m1 = read() ;
if( m1 == 1 )
add( i , j + n ) ;
}
for( int i = 1 ; i <= n ; i++ ){
memset( visit , 0 , sizeof(visit) ) ;
if( dfs(i) )ans ++ ;
}
if( ans >= n )printf("Yes\n");//有足够的匹配
else printf("No\n");
clear();
}
return 0 ;
}
提示：\(clear()\) 函数中
清零时用了多少就清零多少，有效节约因\(memset()\)清零空数组而浪费的时间
3.Dinic网络流解法
如果对网络流没有了解的同学可以参考网络流初步详解，或其他博客。
对于网络流有了解的同学就可以开心地用这道题练习网络流了。
我们再次观察之前处理的图形，如下图。我们发现，求解最大匹配的过程可以演化成单边容量为 \(1\) 的网络流进行求解。
而我们做的，只需在虚拟源点和行之间建立容量为 \(1\) 的边，在在虚拟汇点和列之间建立**容量为 \(1\) **的边即可。
同时在读入时建立行列之间**容量为 \(1\) **的边。
最后跑一遍\(Dinic\)算法。
\(AC\)代码
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3 , N = 40000 + 19 ;
int head[ N*2 ] , d[ N*2 ] , to[ N*10*2 ] , w[ N*10*2 ] , next[ N*10*2 ] ;
int n , s, t , tot = 1 , maxflow = 0 , T ;//maxflow记录答案
inline int read()
{
int s = 0,w = 1;
char g = getchar();
while(g<'0'||g>'9'){if(g=='-')w*=-1;g = getchar();}
while(g>='0'&&g<='9'){s = s*10+g-'0';g = getchar();}
return s*w;
}
queue<int> q ;//广搜时采用队列
void add( int x , int y , int z ){
tot++; to[ tot ] = y , w[ tot ] = z , next[ tot ] = head[ x ] , head[ x ] = tot;
tot++; to[ tot ] = x , w[ tot ] = 0 , next[ tot ] = head[ y ] , head[ y ] = tot;
}//建立边和反向边，注意反向边的流量初始为 0
bool bfs(){//在残量网络上构造分层图
memset( d , 0 , sizeof(d) ) ; //将之前的分层清0，继续跑残量网络找可行增广路
while( q.size() ) q.pop() ; //队列清 0 ;
q.push( s ) ; d[ s ] = 1 ; //将源点加入队列，层数为 1 ，开始广搜
while( q.size() ){
int x = q.front() ; q.pop() ;
for( int i = head[ x ] ; i ; i = next[ i ])
if( w[ i ] && !d[ to[i] ] ){//目标边的流量不为0 且 为被遍历分层
q.push( to[ i ] ) ;
d[ to [ i ] ] = d[ x ] + 1;
if( to[ i ] == t )return 1 ; //找到一条可行增广路
}
}
return 0 ;//未找到，不存在增广路
}
int dinic( int x , int flow ){ //在分层图上进行增广
if( x == t )return flow ;//源点即使汇点，流量不限量
int rest = flow , k ;
for( int i = head[ x ] ; i && rest ; i = next[ i ] )//当前可流入最大流量不为0 ,
if( w[ i ] && d[ to [ i ] ] == d[ x ] + 1 ){//目标路径有剩余流量，且不存在环之类神奇的东西
k = dinic( to[ i ] , min( rest , w[ i ] ) );//继续搜
if( !k )d[ to [ i ] ] = 0 ; //剪枝，如果 k(下一层可流入流量图为 0 )，cut
w[ i ] -= k ;
w[ i ^ 1 ] += k ;//占用k流量，注意反边要加上k，不然无法退回
rest -= k ; //当前节点的剩余汇入流量-k;
}
return flow - rest ; //递归完成
}
void clear(){
T-- ; maxflow = 0 ;
for( int i = 1 ; i<= tot ; i++ )
w[ i ] = to[ i ] = head[ i ] = next[ i ] = 0 ;
tot = 1 ;
}
int main()
{
T = read() ;
while( T != 0 )
{
n = read() ; s = 2*n + 1 ; t = 2*n + 2 ;
for( int i = 1 ; i <= n ; ++i ){
add( s , i , 1 ); add( i + n , t , 1 ) ;
}
for( int i = 1 ; i <= n ; ++i )
for( int j = 1 ; j <= n ; j++ ){
int x = read() ;
if( x ){
add( i , j + n , 1 ) ;
}
}
int flow = 0 ;
while( bfs() ){//存在增广路
while( flow = dinic ( s , inf ))maxflow += flow ;
}
if( maxflow >= n )printf("Yes\n");
else printf("No\n");
clear() ;
}
return 0 ;
}
再次提示：\(clear()\) 函数中
清零时用了多少就清零多少，有效节约因\(memset()\)清零空数组而浪费的时间