BZOJ1854:[SCOI2010]连续攻击游戏——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=1854
https://www.luogu.org/problemnew/show/P1640
lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次?
莫名奇妙的就想到了一个模型,然后脑子瓦特了的情况下竟然写了个正解但是不会论证,emmm……
考虑过权值和权值建边(然而会有重编一定不行),物品和物品建边(显然你不知道属性值了一定不行)。
那就物品和权值建边,对于权值分别向物品连有向边然后跑匈牙利算法即可。
为什么呢?显然,当我们尝试去匹配第i个属性的时候,i-1已经匹配完毕,如果i不能匹配的话就跳出并且输出i-1即可。
(PS:bzoj玩家请注意,不要每次dfs清空vis数组因为这样时间复杂度就不对了,所以需要优化)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=;
const int M=;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int to,nxt;
}e[N*];
int n,m,ans,cnt;
int shu[N],head[M],vis[N];
inline void add(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
bool dfs(int u,int id){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v]!=id){
vis[v]=id;
if(!shu[v]||dfs(shu[v],id)){
shu[v]=u;
return ;
}
}
}
return ;
}
int main(){
n=read();m=M-;
for(int i=;i<=n;i++){
add(read(),i);add(read(),i);
}
for(int i=;i<=m;i++){
if(dfs(i,i))ans++;
else break;
}
printf("%d\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
最新文章
- CYQ.Data 快速开发EasyUI
- zigbee 路由节点丢失后清除 该节点的残余网络信息
- 《Python核心编程》18.多线程编程(二)
- 在 node.js 的 express web 框架中自动注册路由
- wow7.1 xd 新手教程
- Java中Scanner类和BufferReader类之间的区别
- 《嵌入式Linux基础教程》补充阅读建议电子数目下载
- Java Web编程的主要组件技术——Struts核心组件
- busybox下mount nfs的命令
- Android基础之CountDownTimer 倒计时类
- [置顶] IOS培训资料
- 采用ACE登录设施(一)HelloWorld
- 【数论】洛谷P1313计算系数
- httpd添加新模块
- 你学会UI设计了吗?
- [";1";, ";2";, ";3";].map(parseInt)`返回的结果是[1,2,3]?
- Javascript高级编程学习笔记(79)—— 表单(7)选择框脚本
- 洛谷P1019:单词接龙(DFS)
- 关于Bootstrap自定义图标
- linux下安装与部署redis