时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
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最多能连续攻击的次数。
示例1
输入
复制
3
1 2
3 2
4 5
输出
复制
2
备注:
对于30% 的数据，保证N≤1000
对于100% 的数据，保证N≤1000000
题解：
方法一：
经典的二分图匹配
因为每个装备有两个属性，我们必须找到一个与之可以相应匹配的物品，所以我们建立x->i,y->i,两条边，然后我们从属性值1开始从小到大的顺序跑匈牙利算法匹配二分图，当匹配断开，匹配值就是我们要找的答案
方法二：
每个装备两个属性，相当于两个点，中间一条线连接，我们将这些边按照属性值顺序连接在一起，查看哪些点和1在一个连通块里面，这个连通块中间有没有环
样例：
3
1 2
3 2
4 5
建图：
流程：
1匹配1
2匹配2
3匹配2，但是2已经被2匹配了，所以（下面的）2改为匹配1，但（上面）1已经被（下面）1匹配，且1无法更改匹配对象，所以此次3匹配2失败
一旦匹配失败，直接结束，答案为最后的匹配值
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct node{
int v,w,next;
}edge[maxn<<1];
int cnt,head[maxn];
int now,use[maxn],match[maxn];
void add(int u,int v){
edge[++cnt].next=head[u];
edge[cnt].v=v;
head[u]=cnt;
}
bool dfs(int u){
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(use[v]==now)continue;
use[v]=now;
if(!match[v]||dfs(match[v]))
{
match[v]=u;
return 1;
}
}
return 0;
}
int main()
{
int n;
cin>>n;
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
add(x,i);
add(y,i);
}
int ans=0;
for(int i=1;i<=10000;i++)
{
now=i;
if(dfs(i))ans++;
else break;
}
printf("%d\n",ans);
return 0;
}
京公网安备 11010502036488号