【基础练习】【二分图匹配】【匈牙利算法】codevs1022 覆盖题解

清疚 2022-08-09 15:52 208阅读 0赞

题目描述 Description

有一个N×M的单位方格中，其中有些方格是水塘，其他方格是陆地。如果要用1×2的矩阵区覆盖（覆盖过程不容许有任何部分重叠）这个陆地，那么最多可以覆盖多少陆地面积。

![1022.jpg][]

输入描述 Input Description

输入文件的第一行是两个整数N，M  (1<=N，M<=100)，第二行为一个整数K( K<=50)，接下来的K行，每行两个整数X，Y表示K个水塘的行列位置。(1<=X<=N，1<=Y<=M)。

输出描述 Output Description

输出所覆盖的最大面积块（1×2面积算一块）。

样例输入 Sample Input

4 4

1 1

1 4

2 2

4 1

4 2

4 4

样例输出 Sample Output

数据范围及提示 Data Size & Hint

见描述

这题我真没看出来，题解里说一看到1\*2的方块就想到二分图 、

由于是矩形，环的边数一定是偶数，因此属于二分图

如果一个方框是陆地，那么上下左右连双向边，直接跑匈牙利即可

代码

//codevs1022 覆盖 二分图匹配-匈牙利
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=10000+10;
    const int maxm=maxn*10;
    
    int hd[maxn],t[maxn],nxt[maxn],et=0;
    int n,m,k,x,y;
    int mat[maxn],check[maxn];
    bool water[maxn];
    
    void add(int x,int y)
    {
    	et++;
    	t[et]=y;
    	nxt[et]=hd[x];
    	hd[x]=et;
    }
    
    bool dfs(int i)
    {
    	for (int j=hd[i];j;j=nxt[j])
    	{
    		int tt=t[j];
    		if (check[tt]==-1)
    		{
    			check[tt]=i;
    			if (mat[tt]==-1||dfs(mat[tt]))
    			{
    				mat[tt]=i;
    				mat[i]=tt;
    				return true;
    			}
    		}
        }
        return false;
    }
    
    int hungarian()
    {
    	int ans=0;
    	memset(mat,-1,sizeof(mat));
    	for (int i=1;i<=n*m;i++)
    	{
    		if (!water[i]&&mat[i]==-1)
    		{
    			memset(check,-1,sizeof(check));
    			if (dfs(i)) ans++;
    		}
        }
        return ans;
    }
    
    int main()
    {
    	freopen("1.txt","r",stdin);
        scanf("%d%d",&n,&m);
        scanf("%d",&k);
        memset(hd,0,sizeof(hd));
        for (int i=1;i<=k;i++)
        {
        	scanf("%d%d",&x,&y);
        	water[(x-1)*m+y]=true;
        }
        for (int i=1;i<=n;i++)
        {
        	for (int j=1;j<=m;j++)
        	{
        		if (water[(i-1)*m+j]) continue;
        		if (i!=n&&!water[i*m+j])
        		{
        			 add((i-1)*m+j,i*m+j);
        			 add(i*m+j,(i-1)*m+j);
    		    }
    		    if (j!=m&&!water[(i-1)*m+j+1])
    		    {
    		    	add((i-1)*m+j,(i-1)*m+j+1);
    		    	add((i-1)*m+j+1,(i-1)*m+j);
    		    }
        	}
        }
        printf("%d\n",hungarian());
        //for (int i=1;i<=n*m;i++) printf("%d %d\n",i,mat[i]);
        return 0;
    }

今天放古诗文之前，加上句话，基督山伯爵里的，长久以来它一直激励着我

it is your duty.You have a calm, strong mind,Maximilian. Maximilian, you are no ordinary man.

这是你的责任。马西米兰，你有一颗冷静而坚强的头脑；马西米兰，你不是普通人。

今天终于把英文版找出来了。然而个人认为英文不如中文议得好，或许是表达习惯的问题吧，中文的译法，更能让我感受到父亲对儿子的信任，鼓励和殷切的期冀。失意惆怅时，想起这句话，几乎想要潸然泪下，然而父亲目光和语调里透露出的坚定意志仍能激励我打起精神继续前行。

——琵琶起舞换新声，总是关山旧别情

[1022.jpg]: http://codevs.cn/media/image/problem/1022.jpg