首页 > 代码库 > BZOJ 1854 SCOI 2010 游戏 二分图最大匹配
BZOJ 1854 SCOI 2010 游戏 二分图最大匹配
题目大意:现在要打一个BOSS,一个人有n个武器,一个武器有两个属性值,但是一个武器只能攻击一次。这个BOSS需要从1连续递增输出,问输出的最大值为多少。
思路:以前好像做过一个相似的问题,也是这么做的,哪个忘了。。
很明显的二分关系是攻击力和武器,因为一个攻击力需要攻击一次,一个武器只能攻击一次,然后武器和攻击力之间连边,从1开始匹配,什么时候不能匹配了就输出。
memset会T的,时间戳大法好。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1010010 #define BASE 10001 using namespace std; int cnt; int head[MAX],total; int next[MAX << 1],aim[MAX << 1]; int paired[MAX]; int v[MAX],T; inline void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } bool Hungary(int x) { for(int i = head[x]; i; i = next[i]) if(v[aim[i]] != T) { v[aim[i]] = T; if(!paired[aim[i]] || Hungary(paired[aim[i]])) { paired[aim[i]] = x; return true; } } return false; } int main() { cin >> cnt; for(int x,y,i = 1; i <= cnt; ++i) { scanf("%d%d",&x,&y); Add(x,i + BASE); Add(y,i + BASE); } for(int i = 1; i <= BASE; ++i) { ++T; if(!Hungary(i)) { cout << i - 1 << endl; return 0; } } return 0; }
BZOJ 1854 SCOI 2010 游戏 二分图最大匹配
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。