题解 P1129 【[ZJOI2007]矩阵游戏】

## 详谈二分图最大匹配解法 和 网络流 Dinic解法 #### 1.题目分析 #### 2.匈牙利二分图匹配解法 #### 3.Dinic网络流解法 ------------ ## 1.题目分析 由题意得，我们可以对**任意两行**或**两列**进行交换操作。初看似乎没有头绪，那先来分析一组简单数据。 ``` 1 0 0 1 1 0 0 0 1 0 ``` 我们考虑将每一行的**行数**与该行**黑色方块**所在的**列数**连一条边。 然后可以将它进行如**下图**的变化得到答案  我们可以看出，**右图**中的**每一**行列都**至少**有一个符合的匹配（显然）。 进而我们思考，是否是**每一行列**至少存在一组合法匹配的图形合法呢？ #### 答案是的 因为任意两行或者任意两列之间的交换都不会破坏他们的**平衡性**。 #### 也就是说，任意2个黑色方块，如果它们初始状态时不在同一行（列），那么无论如何交换，它们都不会在同一行（列）。 所以我们可以得到第一种解法 匈牙利二分图匹配解法。 ------------ ## 2.匈牙利二分图匹配解法 经过上述分析，交换操作并**不会**影响图的**最大匹配**，我们只需判断**每一行是否都可以合法匹配**即可。 那么显然是一道板子似的**二分图最大匹配**。 **AC代码：** ```cpp #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网络流解法 如果对**网络流**没有了解的同学可以**参考**[网络流初步详解](https://www.luogu.org/blog/sswcdak/bi-ji-wang-lao-liu-chu-bu)，或其他博客。 对于网络流**有了解**的同学就可以**开心**地用这道题**练习网络流**了。 我们再次观察之前处理的图形，如**下图**。我们发现，求解最大匹配的过程可以演化成**单边容量**为 $1$ 的**网络流**进行求解。  而我们做的，只需在**虚拟源点**和**行**之间建立**容量为 $1$** 的边，在在**虚拟汇点**和**列**之间建立**容量为 $1$ **的边即可。 同时在读入时建立**行列**之间**容量为 $1$ **的边。 最后跑一遍**$Dinic$算法**。 **$AC$代码** ```cpp #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()$清零空数组而浪费的时间** ### _本文到此结束，若有不足，恳请大佬指出。_ ### _ 如果你喜欢我的文章，请大力点赞支持！感谢。_