首页 > 代码库 > BZOJ 1191 超级英雄(二分图匹配)
BZOJ 1191 超级英雄(二分图匹配)
把题目作为s集,锦囊作为t集。把每个题目和它可以用的锦囊连边,这样就构成了一个二分图,求出这个二分图最大匹配。
但是这个最大匹配有限制条件,就是对于每个可能的匹配集,如果s集的i点有匹配,那么i-1点一定有匹配。
具体实现,只需要将匈牙利算法稍微改动一下,如果当前没有找到增广路的话,就break。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-3 # define MOD 100000007 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int res=0, flag=0; char ch; if((ch=getchar())==‘-‘) flag=1; else if(ch>=‘0‘&&ch<=‘9‘) res=ch-‘0‘; while((ch=getchar())>=‘0‘&&ch<=‘9‘) res=res*10+(ch-‘0‘); return flag?-res:res; } void Out(int a) { if(a<0) {putchar(‘-‘); a=-a;} if(a>=10) Out(a/10); putchar(a%10+‘0‘); } const int N=1005; //Code begin... struct Edge{int p, next;}edge[N<<1]; int head[N], cnt=1, linker[N], uN; bool used[N]; void add_edge(int u, int v){edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;} bool dfs(int u){ for (int i=head[u]; i; i=edge[i].next) { int v=edge[i].p; if (used[v]) continue; used[v]=true; if (linker[v]==-1||dfs(linker[v])){linker[v]=u; return true;} } return false; } int hungary(){ int res=0; mem(linker,-1); FO(u,0,uN){ mem(used,0); if (dfs(u)) res++; else break; } return res; } int main () { int n, m, u, v; scanf("%d%d",&n,&m); uN=m; FO(i,0,m) scanf("%d%d",&u,&v), add_edge(i,u), add_edge(i,v); printf("%d\n",hungary()); return 0; }
BZOJ 1191 超级英雄(二分图匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。