[二分图匹配] bzoj1854: [Scoi2010]游戏
程序员文章站
2022-05-22 13:35:39
...
bzoj1854: [Scoi2010]游戏:http://www.lydsy.com/JudgeOnline/problem.php?id=1854
dalao说这是最基本的二分图
属性连上武器就ok 了
最神的地方在于如果这个武器已经用过一个属性了它的v就会更新 跑一次find
所以绝对不会出现一个武器用两个属性的情况
太强辣 没怎么做过这种题一开始想的是武器连属性
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int x,y,next;
}a[2100000];
int last[11000],len;
int match[1100000],v[1100000];
int t=0;
void build(int x,int y)
{
len++;
a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;
}
bool find(int x)
{
for (int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if (v[y]!=t)
{
v[y]=t;
if (match[y]==0||find(match[y])==1) {match[y]=x;return 1;}
}
}
return 0;
}
int main()
{
int n,mx=0,ans=0;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
build(x,i);build(y,i);//属性连武器
mx=max(max(x,mx),y);
}
for (int i=1;i<=mx;i++)
{
t++;
if (find(i)) ans++; else break;
}
printf("%d\n",ans);
return 0;
}
推荐阅读
-
洛谷P4589 [TJOI2018]智力竞赛(二分答案 二分图匹配)
-
HDU 1281 棋盘游戏(二分图匹配)
-
POJ 1358 Housing Complexes G++ 二分图匹配 没掌握
-
POJ 1719 Shooting Contest G++ 二分图匹配 没掌握
-
loj#6033. 「雅礼集训 2017 Day2」棋盘游戏(二分图博弈)
-
[Gym 101666]E - Easter Eggs (二分 + 二分图匹配 + 找最小点覆盖(原图最大团) )
-
洛谷 P3386 【模板】二分图匹配
-
P - 奔小康赚大钱 HDU - 2255(二分图最大权完美匹配)
-
SSL1333 地鼠的困境【二分图匹配】【匈牙利算法】
-
BZOJ1059: [ZJOI2007]矩阵游戏(二分图匹配)