连续攻击游戏【P1640洛谷】二分图匹配变形【好题】【每次memset太慢了,用时间戳id。】
lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次?
输入格式
输入的第一行是一个整数N,表示lxhgww拥有N种装备接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值
输出格式
输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。
输入输出样例
3 1 2 3 2 4 5
2
说明/提示
Limitation
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000
来源:SCOI 2010
【总结】
二分图的最大匹配问题,做法很巧妙,但是很难想到。
第一眼看到这个题想到的是将某个物品的两个属性分成左右部点,但是很难解决本题,尤其是在处理一个物品只能用一种属性的时候。所以我们不妨换一种思路,对于物品 ii 的属性 a,ba,b ,分别从 aa 和 bb 向 ii 连一条有向边。将物品的属性当做左部点,编号当做右部点,求最大匹配即可。
这样为什么是正确的呢?我们可以考虑匈牙利算法的具体过程:在匹配值为 ii 的技能时,那么 11 到 i-1i−1 的属性肯定已经匹配完成,所以如果 ii 对应的编号 jj 被匹配了的话,那么就让匹配 jj 的那个属性 pp 再去找别的物品标号匹配,形象地说,就是用别的物品来释放攻击力为 pp 的这个技能,用 jj 这个物品释放攻击力为 ii 的技能。如果找到这样一条增广路,那么就说明当前可以匹配,ans++。
【收获】:每次memset太慢了,用时间戳id。
AC代码:【链接矩阵】
#include<bits/stdc++.h> using namespace std; #define maxn 1000009 int now; inline int read(){ , f = ; ; c = getchar();} + c - ', c = getchar(); return x * f; } int match[maxn]; int vis[maxn]; struct Edge{ int to; int next; }e[*maxn]; ; int head[maxn]; void add(int u,int v){ e[cnt].to=v; e[cnt].next=head[u]; head[u]=cnt++; } int dfs(int u){ int temp; for(int i=head[u];i;i=e[i].next){ temp=e[i].to; if(vis[temp]!=now){ vis[temp]=now; // vis[temp]=1; ||dfs(match[temp])){ match[temp]=u; ; } } } ; } int main(){ int n;int x,y; //scanf("%d",&n); n=read(); ;i<=n;i++){ x=read(); y=read(); add(x,i); add(y,i); } ; ;i<=n;i++){ now++; if(dfs(i)) ans++; else{ break; } } printf("%d\n",ans); ; }
【vector存图】
#include<bits/stdc++.h> using namespace std; #define maxn 1000009 int match[maxn]; int vis[maxn]; int id; vector<int> v[maxn]; int dfs(int u){ ;i<v[u].size();i++){ int temp=v[u][i]; if(vis[temp]!=id){ vis[temp]=id; ||dfs(match[temp])){ match[temp]=u; ; } } } ; } int main(){ int n; scanf("%d",&n); ;i<=n;i++){ int x,y; scanf("%d%d",&x,&y); v[x].push_back(i); v[y].push_back(i); } memset(match,,sizeof(match)); ; ;i<=n;i++){ id++; if(dfs(i)) ans++; else{ break; } } cout<<ans<<endl; ; }
最新文章
- Entity Framework 6 Recipes 2nd Edition(12-5)译 ->; 自动删除相关联实体
- Python之实用的IP地址处理模块IPy
- 关于博弈论中的一硬币正反问题的分析<;二>;
- <;-0基础学python.第2课->;
- STM32正交编码器驱动电机
- RouterOS DNS劫持 -- A记录
- The declared package does not match the expected package
- 超简单的处理JSON格式和JSON数组格式的String
- 【pyQuery分析实例】分析体育网冠军联盟比赛成绩
- Matlab:拟合(1)
- BOOST中如何实现线程安全代码
- HBase配置&;启动脚本分析
- js编程风格
- Oracle EBS-SQL (QA-2):检查接收未检验.SQL
- Centos7 安装高版本php
- JS实现轻量级计算器
- PDO错误调试
- GDAL创建图像提示Driver xxx does not support XXX creation option的原因
- 1.9 From Native to HTML5
- php实现无限级分类查询(递归、非递归)