首页 > 代码库 > vijos p1204——CoVH之柯南开锁

vijos p1204——CoVH之柯南开锁

2024-08-19 17:40:21   224人阅读

背景

随着时代的演进,困难的刑案也不断增加...
但真相只有一个
虽然变小了,头脑还是一样好,这就是名侦探柯南!

描述

[CoVH06]
面对OIBH组织的嚣张气焰, 柯南决定深入牛棚, 一探虚实.
他经过深思熟虑, 决定从OIBH组织大门进入...........

OIBH组织的大门有一个很神奇的锁.
锁是由M*N个格子组成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子给按下去.
技术分享
如果柯南能在组织限定的次数内将所有格子都按下去, 那么他就能够进入总部. 但是OIBH组织不是吃素的, 他们的限定次数恰是最少次数.

请您帮助柯南计算出开给定的锁所需的最少次数.

格式

输入格式

第一行 两个不超过100的正整数N, M表示矩阵的长和宽
以下N行 每行M个数 非0即1 1为凸起方格

输出格式

一个整数 所需最少次数

样例1

样例输入1

4 40000010100000100

样例输出1

2

限制

全部1秒

 

用到二分图，将x和y作为点集，求最大匹配即可。

代码几乎和poj P1274的牛栏一模一样。O(n³)

 

 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int maxn=205; 7 bool map[maxn][maxn]; 8 int n,m; 9 bool vis[maxn];10 int match[maxn];11 inline bool dfs(int x)12 {13     for(int i=1;i<=m;i++)14     {15         if(map[x][i]&&!vis[i])16         {17             vis[i]=true;18             if(match[i]==-1||dfs(match[i]))19             {20                 match[i]=x;21                 return true;22             }23         }24     }25     return false;26 }27 inline void hungary()28 {29     int count=0;30     for(int i=1;i<=n;i++)31     {32         memset(vis,false,sizeof(vis));33         if(dfs(i))count++;34     }35     printf("%d",count);36     return ;37 }38 inline void gg()39 {40     scanf("%d%d",&n,&m);41     memset(map,false,sizeof(map));42     memset(match,-1,sizeof(match));43     for(int i=1;i<=n;i++)44     {45         for(int j=1;j<=m;j++)46         {47             int x=getchar();48             while(x<‘0‘||x>‘9‘)x=getchar();49             if(x==‘1‘)50             map[i][j]=true;51         }52     }53     hungary();54     return ;55 }56 int main()57 {58     gg();59     return 0; 60 }

 

 

 

vijos p1204——CoVH之柯南开锁


联系
我们