首页 > 代码库 > HDU--1054--Strategic Game【最小点覆盖】
HDU--1054--Strategic Game【最小点覆盖】
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1054
题意:一个熊孩子玩策略游戏,他需要用最少的士兵守卫最多的道路,如果这个顶点有士兵,则和这个点相连的所有边都会被保护,问保护所有的道路最少需要的士兵数量。
思路:这实际上就是一个最小点覆盖,二分图的最小点覆盖 == 最大匹配,这不是一个二分图,我们把n个点扩成2 * n个,把他转换为二分图,最后最大匹配再除以2就是原图的最大匹配。
Hopcroft-Karp增广模板
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 1510 #define eps 1e-7 #define INF 0x3F3F3F3F //0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 1313131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 /* 二分图匹配(Hopcroft-Carp的算法)。 顶点下标从0开始 调用:res=MaxMatch(); Nx,Ny要初始化!!! 时间复杂大为 O(V^0.5 E) 适用于数据较大(点较多)的二分匹配 */ struct node{ int v,next; }edge[MAXN*MAXN]; int head[MAXN],cnt; int Mx[MAXN],My[MAXN],Nx,Ny; int dx[MAXN],dy[MAXN],dis; bool vis[MAXN]; void add_edge(int a,int b){ edge[cnt].v = b; edge[cnt].next = head[a]; head[a] = cnt++; } bool searchP(){ queue<int>q; dis = INF; memset(dx,-1,sizeof(dx)); memset(dy,-1,sizeof(dy)); for(int i = 0; i < Nx; i++) if(Mx[i] == -1){ q.push(i); dx[i] = 0; } while(!q.empty()){ int u = q.front(); q.pop(); if(dx[u] > dis) break; for(int i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].v; if(dy[v] == -1){ dy[v] = dx[u] + 1; if(My[v] == -1) dis = dy[v]; else{ dx[My[v]] = dy[v] + 1; q.push(My[v]); } } } } return dis != INF; } bool DFS(int u){ for(int i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].v; if(!vis[v] && dy[v] == dx[u] + 1){ vis[v] = 1; if(My[v] != -1 && dy[v] == dis) continue; if(My[v] == -1 || DFS(My[v])){ My[v] = u; Mx[u] = v; return 1; } } } return 0; } int MaxMatch(){ int res = 0; memset(Mx,-1,sizeof(Mx)); memset(My,-1,sizeof(My)); while(searchP()){ memset(vis,0,sizeof(vis)); for(int i = 0; i < Nx; i++) if(Mx[i] == -1 && DFS(i)) res++; } return res; } int main(){ int n,i,j; int a,m,b; while(scanf("%d", &n)!=EOF){ cnt = 0; memset(head,-1,sizeof(head)); for(i = 0; i < n; i++){ scanf("%d:(%d)", &a, &m); while(m--){ scanf("%d", &b); add_edge(a,b); add_edge(b,a); } } Nx = Ny = n; int ans = MaxMatch(); printf("%d\n", ans / 2); } return 0; }
HDU--1054--Strategic Game【最小点覆盖】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。