HDU 3026 Chinese Chess 二分匹配(TLE...)

2024-06-15 11:18

本文主要是介绍HDU 3026 Chinese Chess 二分匹配(TLE...),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

求有多少个点,满足不选这个点最大匹配减少,超时了,挖个坑, 以后实力够了在来填坑。。。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 10010;
const int maxm = 10010;
bool vis[maxn];
int y[maxn];
int n, m;
vector<int> G[maxn];
int b[maxn];
int nowx, nowy, flag;
bool dfs(int u)
{
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(vis[v] || (flag && u == nowx && v == nowy))
continue;
vis[v] = true;
if(y[v] == -1 || dfs(y[v]))
{
y[v] = u;
return true;
}
}
return false;
}
int match()
{
int ans = 0;
memset(y, -1, sizeof(y));
for(int i = 0; i < n; i++)
{
memset(vis, false, sizeof(vis));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
int cas = 1;
int T;
int k;
//scanf("%d", &T);
while(scanf("%d %d %d", &n, &m, &k) != EOF)
{
flag = 0;
for(int i  = 0; i <= n; i++)
G[i].clear();
memset(b, 0, sizeof(b));
while(k--)
{
int u, v;
scanf("%d %d", &u, &v);
u--;
v--;
G[u].push_back(v);
}
int ans = match();
int sum = 0;
memset(b, 0, sizeof(b));
for(int j = 0; j < m; j++)
if(y[j] != -1)
b[y[j]] = 1;
flag = 1;
for(int i = 0; i < m; i++)
{
if(y[i] == -1)
continue;
int temp = y[i];
y[i] = -1;
nowx = temp;
nowy = i;
b[temp] = 0;
int flag2 = 0;
for(int j = 0; j < n; j++)
{
memset(vis, 0, sizeof(vis));
if(!b[j] && dfs(j))
flag2 = 1;
if(flag2)
break;
}
if(!flag2)
{
sum++;
y[i] = temp;
}
}
printf("Board %d have %d important blanks for %d chessmen.\n", cas++, sum, ans);
}
return 0;
}

这篇关于HDU 3026 Chinese Chess 二分匹配(TLE...)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063298

相关文章

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ