[传送门] ( https://www.luogu.org/problemnew/show/P1640 )
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
- Sample Output
- 2
- HINT
对于 30% 的数据, 保证 N <=1000
对于 100% 的数据, 保证 N < =1000000
Solution
二分图匹配 通过更改 vis 标记减少 memset
- Code
- //By Menteur_Hxy
- #include <vector>
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- #include <iostream>
- #include <algorithm>
- #define F(i,a,b) for(register int i=(a);i<=(b);i++)
- using namespace std;
- int read() {
- int x=0,f=1; char c=getchar();
- while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}
- while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
- return x*f;
- }
- const int N=1000010;
- int n,ans;
- int vis[N],fr[N];
- vector<int> V[N];
- bool dfs(int x) {
- int siz=V[x].size();
- F(i,0,siz-1) {
- int v=V[x][i];
- if(vis[v]!=ans+1) {
- vis[v]=ans+1;
- if(!fr[v]||dfs(fr[v])) {
- fr[v]=x;
- return 1;
- }
- }
- }
- return 0;
- }
- int main() {
- n=read();
- F(i,1,n) {
- int x=read(),y=read();
- V[x].push_back(i);
- V[y].push_back(i);
- }
- F(i,1,10000) {
- if(!dfs(i)) break;
- ans++;
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2729529.html