bzoj1854: [Scoi2010]游戏(匈牙利) / GDKOI Day2 T2(最大流)

　　题目大意：有n(<=1000000)个装备，每个装备有两个属性值(<=10000)，每个装备只能用一次，使用某一个值，攻击boss必须先使用属性为1的，再使用属性为2的，再使用属性为3的，以此类推······问最多攻击多少次。

　　每个武器和他的两个属性值连边，跑匈牙利。

　　学会了新的技巧，可以省掉1w个memset(这题是真·1w个 2333333)。

代码如下：

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

using namespace std;

struct poi{int too,pre;}e[];

int n,x,y,t,tot,ans,num,lin[],last[],v[];

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

bool dfs(int x)

{

    for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)

    if(v[too]!=t)

    {

        v[too]=t;

        if((!lin[too])||dfs(lin[too]))

        {

            lin[too]=x;

            return ;

        }

    }

    return ;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d %d",&x,&y),add(x,i),add(y,i);

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

    {

        ++t;

        if(dfs(i))ans++;

        else break;

    }

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

}

　　虽然初三狗没法去GDKOI，但是还是问到了GDKOI的题意OWO（金中大爷都好劲啊！

　　GDKOI Day2T2挺像的，n个士兵，每个兵有两个属性值，每个士兵进攻一次，只能选择一个属性值，攻击boss必须属性值高于h，每次派出的士兵属性值要比前一次高，问最多攻击多少次。

　　源点和每个士兵连边容量为1，每个士兵和两个属性值连边，大于h的属性值和汇点连边容量为1，跑最大流。

巴特西

bzoj1854: [Scoi2010]游戏(匈牙利) / GDKOI Day2 T2(最大流)

最新文章

热门文章