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

[二分图匹配] 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;
}