[SCOI2010] 连续攻击游戏

题意

游戏里有很多的装备,每种装备都有 2 个属性,属性值为 [1,10000] 之间的数。

使用某种装备只能使用该装备的一个属性。每种装备最多只能使用一次。

要求使用的装备的属性值从 1 开始连续递增,想知道他最多能连续攻击多少次?

分析

一道不能套网络流的二分图。。。

我们将属性与装备编号连边,然后从属性 1 开始依次匹配装备,直到无法匹配了就输出

这个过程显然就是匈牙利算法啦

随机一个匈牙利算法

代码

#include<cstdio>
using namespace std;
const int N=2e6+6;// 空间要开够!!
int n;
struct qxx{int nex,t;};
qxx e[N*2];
int h[N],cnt=1;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}

int vis[N],match[N],cur;// 时间戳标记
bool dfs(int u){//u 是左部结点
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
        if(vis[v]==cur)continue;
        vis[v]=cur;
        if(!match[v]||dfs(match[v]))return match[v]=u,1;
    }
    return 0;
}
int hungarian(){
    int res=0;
    for(int i=1;i<=n*2;i++){if(match[i])continue;
        ++cur;
        if(dfs(i))res++;
        else return res;
    }
    return res;
}

int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++){int u,v;
        scanf("%d%d",&u,&v);
        //i -> i+n
        add_path(u,i+n),add_path(i+n,u);
        add_path(v,i+n),add_path(i+n,v);
    }
    printf("%d",hungarian());
    return 0;
}

 上一篇
[NOI2009] 变换序列 [NOI2009] 变换序列
题意在 的整数序列中,定义两个数 的距离为 . 现要求构造一个序列 ,使得每一个
2019.01.15
下一篇 
[ZJOI2010] 网络扩容 [ZJOI2010] 网络扩容
题意给定一张有向图,每条边都有容量 和扩容费用 。这里扩容费用指将容量扩大 1 所需的费用。求: 在不扩容的情况下,1 到 N 的最大流. 将 1 到 N 的最大流增加 K 所需的最小扩容费用. Subtask1
2019.01.14
  目录