详谈二分图最大匹配解法 和 网络流 Dinic解法
1.题目分析
2.匈牙利二分图匹配解法
3.Dinic网络流解法
1.题目分析
由题意得，我们可以对任意两行或两列进行交换操作。初看似乎没有头绪，那先来分析一组简单数据。
10 0 11 0 00 1 0
我们考虑将每一行的行数与该行黑色方块所在的列数连一条边。
然后可以将它进行如下图的变化得到答案
我们可以看出，右图中的每一行列都至少有一个符合的匹配（显然）。
进而我们思考，是否是每一行列至少存在一组合法匹配的图形合法呢？
答案是的
因为任意两行或者任意两列之间的交换都不会破坏他们的平衡性。
也就是说，任意2个黑色方块，如果它们初始状态时不在同一行（列），那么无论如何交换，它们都不会在同一行（列）。
所以我们可以得到第一种解法 匈牙利二分图匹配解法。
2.匈牙利二分图匹配解法
经过上述分析，交换操作并不会影响图的最大匹配，我们只需判断每一行是否都可以合法匹配即可。
那么显然是一道板子似的二分图最大匹配。
AC代码：
#includeusing 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\)代码
#includeusing 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 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()\)清零空数组而浪费的时间
本文到此结束，若有不足，恳请大佬指出。
### _ 如果你喜欢我的文章，请大力点赞支持！感谢。_