1854. [SCOI2010]游戏【二分图】
2024-10-14 23:44:14
Description
lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次?
Input
输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值
Output
输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。
Sample Input
3
1 2
3 2
4 5
1 2
3 2
4 5
Sample Output
2
HINT
【数据范围】
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000
之前可能用了个假的匈牙利……也可能是我sb了
二分图之前一直用的邻接矩阵……慢的要死
改成邻接表后果然快到飞起……
然后匈牙利还学到一个新技巧:算法的for循环里不用重复memset
令ID等于当前循环的i,然后find里判断的时候就判断used的值是不是等于ID
不等于就是false,等于就是true
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node
{
int x,y,z;
} a[];
struct node1
{
int to,next;
} edge[];
int n,To[],head[],num_edge;
int used[],ID; bool cmp(node a,node b)
{
return a.z<b.z;
}
void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
}
inline int get()
{
char c;
int x=,f=;
c=getchar();
while (c<''||c>'')
{
if (c=='-') f=-;
c=getchar();
}
while (c>=''&&c<='')
{
x=x*+c-'';
c=getchar();
}
return x*f;
}
bool find(int x)
{
for (int i=head[x]; i!=; i=edge[i].next)
{
if (used[edge[i].to]!=ID)
{
used[edge[i].to]=ID;
if (To[edge[i].to]== || find(To[edge[i].to]))
{
To[edge[i].to]=x;
return true;
}
}
}
return false;
}
int main()
{
n=get();
for (int i=; i<=n; ++i)
{
a[i].x=get(),a[i].y=get();
add(a[i].x,i);
add(a[i].y,i);
}
int ans=;
for (int i=; i<=; ++i)
{
ID=i;
if (!find(i))
break;
++ans;
}
printf("%d",ans);
}
最新文章
- Redis-分片
- Dynamics AX 2012 R2 AIF 错误 &#39;/MicrosoftDynamicsAXAif60&#39; 应用程序中的服务器错误
- webpack-dev-server、webpack-dev-middleware、webpack-hot-middleware区别
- Introduction to Project Management(II)
- ref和out的区别?
- 几款开源的图形化Redis客户端管理软件推荐
- JWS-webservice 与Axis2-webservice的高速实现
- 深拷贝与浅拷贝(mutableCopy与Copy)详解 iOS
- C# 汉子增加UTF-8头
- Java并发系列[9]----ConcurrentHashMap源码分析
- 【转】getopt模块,实现获取命令行参数
- Python - 使用objgraph生成对象引用关系图
- Git基础(三) 跟踪文件
- 51nod 1805 小树 (组合数模板,逆元公式)
- 三 oracle 用户管理一
- 浅谈padding
- webkit内核的浏览器为什么removeAttribute(&#39;style&#39;)会失效?
- BZOJ2705 SDOI2012 Longge的问题 【欧拉函数】
- css ! important 兼容性的一点测试
- histroy.back和histroy.go的区别