题意:
lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。
游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次?
题解:
看了看提交AC的一些代码,一看代码好短,但是想了想这些代码好像有点问题,好像是测试点不够强,所以AC了。
然后去看了看大神们的题解,原来是用二分图,这题把图建好就差不多是一个模板题吧。
就注意以下如何建图就可以了。
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
add(x,i);
add(y,i);
}代码:
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstdio>
#include <string.h>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<cmath>
#include <math.h>
#include<algorithm>
//#define int long long
using namespace std;
const int maxn = 1e6+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
struct node{
int next,to;
}edge[maxn*2];
int head[maxn];
int match[maxn];
bool visited[maxn];
int cnt=0;
void add(int u,int v){
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
bool dfs(int x){
for(int i=head[x];~i;i=edge[i].next){
int v=edge[i].to;
if(!visited[v]){
visited[v]=true;
if(!match[v]||dfs(match[v])){
match[v]=x;
return true;
}
}
}
return false;
}
signed main()
{
int n;
memset(head,-1,sizeof head);
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
add(x,i);
add(y,i);
}
for(int i=1;i<maxn;i++){
memset(visited,0,sizeof visited);
if(!dfs(i)){
cout<<i-1<<endl;
return 0;
}
}
return 0;
}

京公网安备 11010502036488号