题目链接：

https://www.luogu.org/problemnew/show/P1640

分析：

这道题用二分图来解决即可.应该可以作为网络流中的模板题来食用，

每一个武器有两个属性，但是只能取一个用，由此我们便可以想到与二分图挂钩。

二分图匹配当中，一个点只能和一个点匹配

问题当中要从小到大使用所有属性，所以肯定要有以1…10000属性为点的一侧

把装备放在另一侧，装备和它的两个属性连边.

(也就相当于从左到右一连，再从右到左一连，才相当于用了两个属性。

从小到大匹配属性点，

因为题目要求必须要每个技能依次释放，所以要有else break环节，这是一个网络流二分图中需要重点注意的环节，有时要加而有时不要，这里要加上还是比较好理解的。

代码：

#include<cstdio>

#include<vector>

#include<cmath>

using namespace std;

vector<int>v[10005];

int vis[1000005],link[1000005];

int t;

bool find(int x)//二分图模板，简单而且理解也不难，墙裂建议借鉴

{

    for(int i=0;i<v[x].size();i++)

    {

        int p=v[x][i];

        if(vis[p]!=t)

        {

            vis[p]=t;

            if(link[p]==0||find(link[p]))

            {

                link[p]=x;

                return 1;

            }

        }

    }

    return 0;

}

int main()

{

    int n;

    scanf("%d",&n);

    int maxf=0;

    for(int i=1;i<=n;i++)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        v[a].push_back(i);

        v[b].push_back(i);

    }

    int cnt=0;

    for(int i=1;i<=n;i++)

    {

        t++;

        if(find(i))

        {

            cnt++;

        }

        else

        break;

    }

    printf("%d\n",cnt);

    return 0;

}

巴特西

洛谷P1640 [SCOI2010]连续攻击游戏题解

题目链接：

分析：

代码：

最新文章

热门文章

巴特西

洛谷P1640 [SCOI2010]连续攻击游戏 题解

题目链接：

分析：

代码：

最新文章

热门文章

洛谷P1640 [SCOI2010]连续攻击游戏题解