HDU-2119-Matrix(最大匹配)

链接:https://vjudge.net/problem/HDU-2119#author=Smilencer

题意:

众所周知,tyz是一个写bug小能手,以至于如果没有队友的帮助,就ac不了程序。 
今天可怜的XJL又被抓来出数据debug了,你要帮助他以最少的样例消灭所有程序的bug 
数据以矩阵的形式表示出来,整个矩阵中只包含0,1两个数。其中1代表一个bug。 
已知每出一个样例可以消灭一行或者一列的bug,即把一行或一列所有的1变成0。 
你的任务是求出最少需要找多少个样例才能使得整个程序没有bug,即矩阵中的1全部被清除

思路:

x,y建立二分图。

代码:

#include <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <queue>
#include <math.h>
#include <cstdio>
#include <set>
#include <iterator>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXN = 5e3+10;
int Next[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

vector<int> G[MAXN];
int Map[110][110];
int Link[MAXN], Vis[MAXN];
int n, m, k;

bool Dfs(int x)
{
    for (int node = 1;node <= m;node++)
    {
        if (Map[x][node] && Vis[node] == 0)
        {
            Vis[node] = 1;
            if (Link[node] == -1 || Dfs(Link[node]))
            {
                Link[node] = x;
                return true;
            }
        }
    }
    return false;
}

int Solve()
{
    memset(Link, -1, sizeof(Link));
    int cnt = 0;
    for (int i = 1;i <= n;i++)
    {
        memset(Vis, 0, sizeof(Vis));
        if (Dfs(i))
            cnt++;
    }
    return cnt;
}

int main()
{
    while (~scanf("%d", &n) && n)
    {
        scanf("%d", &m);
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++)
                scanf("%d", &Map[i][j]);
        int cnt = Solve();
        printf("%d\n", cnt);
    }

    return 0;
}

  

原文地址:https://www.cnblogs.com/YDDDD/p/10872326.html

时间: 05-15

HDU-2119-Matrix(最大匹配)的相关文章

HDU 2119 Matrix 简单二分匹配

行做x集,列做y集,1就给该行该列连一条边,输出最大匹配边即可 #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<set> using namespace std; #define N 105 int lef[N], pn;//lef[v]表示Y集的点v 当前连接的点 , pn为x点集的

hdu 2119 Matrix

Matrix http://acm.hdu.edu.cn/showproblem.php?pid=2119 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description Give you a matrix(only contains 0 or 1),every time you can select a row or a column and dele

HDU——2119 Matrix

    题目大意: 给你一个矩阵(只包含0或1),每次你可以选择一行或一列,并删除这一行或这个列中的所有“1”.您的任务是给出删除矩阵中所有“1”的最小时间. 思路: 我们要将所有的1都删去,那样我们对于1的位置的行与列连边,再把这两个(列和边)看作是两个集合.求它的最大匹配数. 一个很简单的二分图的板子.. 代码: #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream>

POJ 2135 Farm Tour &amp;&amp; HDU 2686 Matrix &amp;&amp; HDU 3376 Matrix Again 费用流求来回最短路

累了就要写题解,最近总是被虐到没脾气. 来回最短路问题貌似也可以用DP来搞,不过拿费用流还是很方便的. 可以转化成求满流为2 的最小花费.一般做法为拆点,对于 i 拆为2*i 和 2*i+1,然后连一条流量为1(花费根据题意来定) 的边来控制每个点只能通过一次. 额外添加source和sink来控制满流为2. 代码都雷同,以HDU3376为例. #include <algorithm> #include <iostream> #include <cstring> #in

HDU 4902 Matrix multiplication

点击打开链接 Matrix multiplication Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2113    Accepted Submission(s): 956 Problem Description Given two matrices A and B of size n×n, find the product o

HDU 2686 Matrix(最大费用最大流+拆点)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2686 和POJ3422一样 删掉K把汇点与源点的容量改为2(因为有两个方向的选择)即可 #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> const int ma

HDU多校赛第9场 HDU 4965Fast Matrix Calculation【矩阵运算+数学小知识】

难度上,,,确实,,,不算难 问题是有个矩阵运算的优化 题目是说给个N*K的矩阵A给个K*N的矩阵B(1<=N<=1000 && 1=<K<=6),先把他们乘起来乘为C矩阵,然后算C^(N*N) 相当于 ABABABABABABAB...=(AB)^(N*N) 不如 A(BA)^(N*N-1)B 因为BA乘得K*K的矩阵,K是比较小的 #include <cstdio> #include <cstdlib> #include <cstr

HDU 2830 Matrix Swapping II (DP,最大全1矩阵)

题意  给你一个n*m矩阵  每列都可以随便交换位置   求最优交换后最大的全1子矩阵 又是HDU 1505 1506的变种  但这个更容易了  因为每列都可以交换位置了   那么这一行中所有比i高的都可以与i相邻了  只需要统计这一行有多少个比i高就行了   可以在算出每一行后  把高度大的放前面去  用num[i]记录排序后的列原来的数  这样就有j列比h[i][num[j]]高了  最后的答案也就是max(j*h[i][num[j]]) #include<cstdio> #include

HDU 4920 Matrix multiplication(矩阵相乘)

各种TEL,233啊.没想到是处理掉0的情况就可以过啊.一直以为会有极端数据.没想到竟然是这样的啊..在网上看到了一个AC的神奇的代码,经典的矩阵乘法,只不过把最内层的枚举,移到外面就过了啊...有点不理解啊,复杂度不是一样的吗.. Matrix multiplication Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 640 

hdu 4920 Matrix multiplication(矩阵乘法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4920 Matrix multiplication Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 989    Accepted Submission(s): 396 Problem Description Given two matr