欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1640 [SCOI2010]连续攻击游戏:(二分图)

程序员文章站 2024-03-17 15:22:58
...

lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次?

输入:
3
1 2
3 2
4 5
输出:
2

初次看的时候,想用装备建图模型,可以接在连续用的装备建一条边,然后这个模型似乎不太适用于二分图,当时想了一个有向图最长路的解法(未实现),但不能访问过去已经访问过的点,而新的起点又要把前面的标记清0,觉得不好下手,遂放弃。

仔细读题,发现攻击值的范围只有10000,想到一个模型,用装备连边到攻击数值,开一个1000000的容器用来存装备,建边,要保证1一定被匹配,但发现好像不太能保证1一定被匹配,且匹配不一定是连续的。

反过来,用数值建边到装备,因为匈牙利算法是一个连续的过程,我们从1开始匹配,如果能找到装备可以匹配就匹配,如果找不到了,就直接break。这是正解模型

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int n,x,y,used[100 * maxn],cy[100 * maxn];
vector<int> g[maxn];
int find(int u){
 	for(int i = 0; i < g[u].size(); i++){
  		int v = g[u][i];
  		if(!used[v]){
   			used[v] = 1;
   			if(!cy[v] || find(v)){
    				cy[v] = u;
    				return 1;
   			}
  		}
 	}
 	return 0;
}
int match(){
 	int res = 0;
 	for(int i = 1; i <= 10000; i++){
  		if(find(i)) res++;
  		else break;
 	}
 	return res;
}
int main(){
 	scanf("%d",&n);
 	for(int i = 1; i <= n; i++){
  		scanf("%d%d",&x,&y);
  		g[x].push_back(i);
  		g[y].push_back(i);
 	}
 	printf("%d\n",match());
 	return 0;
}
相关标签: 二分图