题解[ZJOI2007]矩阵游戏

Love The Way You Lie 2021-12-22 05:49 209阅读 0赞

## 详谈二分图最大匹配解法 和 网络流 Dinic解法 ##

#### 1.题目分析 ####

#### 2.匈牙利二分图匹配解法 ####

#### 3.Dinic网络流解法 ####

--------------------

## 1.题目分析 ##

由题意得，我们可以对**任意两行**或**两列**进行交换操作。初看似乎没有头绪，那先来分析一组简单数据。

1
    0 0 1
    1 0 0
    0 1 0

我们考虑将每一行的**行数**与该行**黑色方块**所在的**列数**连一条边。

然后可以将它进行如**下图**的变化得到答案

![007BSLUzgy1fzj2ax77kuj30ro0n6jte.jpg][]

我们可以看出，**右图**中的**每一**行列都**至少**有一个符合的匹配（显然）。

进而我们思考，是否是**每一行列**至少存在一组合法匹配的图形合法呢？

#### 答案是的 ####

因为任意两行或者任意两列之间的交换都不会破坏他们的**平衡性**。

#### 也就是说，任意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网络流解法 ##

如果对**网络流**没有了解的同学可以**参考**[网络流初步详解][Link 1]，或其他博客。

对于网络流**有了解**的同学就可以**开心**地用这道题**练习网络流**了。

我们再次观察之前处理的图形，如**下图**。我们发现，求解最大匹配的过程可以演化成**单边容量**为 \\(1\\) 的**网络流**进行求解。

![007BSLUzgy1fzj2awrbr0j30nm0f7wg6.jpg][]

而我们做的，只需在**虚拟源点**和**行**之间建立**容量为 \\(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()\\)清零空数组而浪费的时间**

### *本文到此结束，若有不足，恳请大佬指出。* ###

\#\#\# \_ 如果你喜欢我的文章，请大力点赞支持！感谢。\_

转载于:https://www.cnblogs.com/ssw02/p/10404466.html

[007BSLUzgy1fzj2ax77kuj30ro0n6jte.jpg]: /images/20211220/cd146f997e884fcba8ba3b5ed4f59328.png
[Link 1]: https://www.cnblogs.com/ssw02/p/10390214.html
[007BSLUzgy1fzj2awrbr0j30nm0f7wg6.jpg]: /images/20211220/5a6446d30be34f148955e385d993249f.png