EOJ 2069/POJ 3041 Asteroids「二分图匹配」_每次删除一行或一列,求最小操作次数-程序员宅基地

题目简介

N×N网格中有若干个小行星，武器每次发射可以清除一行或一列，问最少需要发射多少次才能清除全部小行星。

说明

所有小行星横坐标为一个点集，纵坐标为另一个点集。对于每个小行星，在其横坐标与纵坐标之间连一条边，则问题转化为求二分图最小点覆盖。又因为二分图最小点覆盖==二分图最大匹配，所以直接跑匈牙利就行。

#include<bits/stdc++.h>
using namespace std;

bool path[505][505], v[505];
int ast[505], n, k;

bool dfs(int x)
{
    for (int i = 1; i <= n; ++i)
        if (!v[i] && path[x][i]) {
            v[i] = 1;
            if (!ast[i] || dfs(ast[i])) {
                ast[i] = x;
                return 1;
            }
        }
    return 0;
}

int main()
{
    int x, y, ans = 0;
    cin >> n >> k;
    while (k--) {
        scanf("%d%d", &x, &y);
        path[x][y] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        memset(v, 0, sizeof(v));
        if (dfs(i)) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}

本文链接：https://blog.csdn.net/fwq990720/article/details/79186153

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

技术干货 | 开始使用 Redis_navicat连接redis-程序员宅基地

文章浏览阅读1.4k次。本教程介绍了开始使用 Redis 所需的基本概念。未来几周将会有更多关于 Redis 的文章，所以一定要经常回来看看呀！_navicat连接redis

DB2 SQLSTATE 消息大全_sqlsate-42524-程序员宅基地

文章浏览阅读2.1k次。本文列示 SQLSTATE 及其含义。SQLSTATE 是按类代码进行分组的。SQLSTATE 类代码类 00 完全成功完成 01 警告 02 无数据 07 动态 SQL 错误 08 连接异常 09 触发操作异常 0A 功能部件不受支持 0D 目标类型规范无效 0F 无效标记 0K RESIGNAL 语句无效 0N SQL/XML_sqlsate-42524

redis 配置详解 -- sentinel 配置详解_redisnot enough paramters available-程序员宅基地

文章浏览阅读228次。一、redis.conf 配置项说明如下：1. Redis默认不是以守护进程的方式运行，可以通过该配置项修改，使用yes启用守护进程daemonize no2. 当Redis以守护进程方式运行时，Redis默认会把pid写入/var/run/redis.pid文件，可以通过pidfile指定pidfile /var/run/redis.pid3. 指定Redis监..._redisnot enough paramters available

The server time zone value ‘�й��׼ʱ��‘ is..._dolphinscheduler the server time zone value ' й-程序员宅基地

文章浏览阅读159次。The server time zone value ‘�й��׼ʱ��’ is unrecognized or represents more than one time zone. You must configure either the server or JDBC driver (via the ‘serverTimezone’ configuration property) to use a more specific time zone value if you want to utiliz_dolphinscheduler the server time zone value ' й

el-dialog 垂直居中-程序员宅基地

文章浏览阅读783次，点赞11次，收藏10次。哈哈哈，最近莫名其妙的喜欢分享一些开发中的细枝末叶，其实更想将这些东西形成系统的材料进行分享，奈何中年大叔心有余而力不足，只好一点点的随着心情去崩发出来，写多少字儿就多少字吧，总之看着实用，有价值就好。el-dialog这个布局不知道遵循什么用户体验标准，弹出来这个页面体验确实不够好，闲来无事看到了，就研究研究。_el-dialog 垂直居中

光耦振荡器_光耦pnp输出-程序员宅基地

文章浏览阅读487次，点赞7次，收藏9次。随着反馈电容C1充电，是的电路结束输出饱和状态，一旦输出退出饱和，紧接着下来，正反馈是的输出立刻进入了截止状态。核心器件是一个光耦，型号为 PC817C， R2， 10k欧姆，提供了输入端口的偏置电流。根据前面的分析，如果改变R3的大小，将其提升到200欧姆，此时，对的震荡信号中，输出高电平的时间就会增加。文仿真了一个给予光耦的震荡电路，有人在这个电路的基础上增加了一个功率PNP三极管，形成了一个反激逆变电路，这样可以产生隔离的逆变直流电源。_光耦pnp输出