首页 > 学院 > 开发设计 > 正文

jzoj 5000. 【NOI2017模拟3.4】保镖 hall定理+搜索

2019-11-06 06:29:32
字体:
来源:转载
供稿:网友

题意

现在有一副若干条边的二分图,左边有n个点 ,右边有m个点 ,左边每个点有权值w[i],右边每个有权值v[i] 。一个图的子图定义为他端点的子集。一个合法的子图满足以下两个条件: 选出的点权和大于等于限制t 并且可以从图中选出若干条边,使得二分图中每个点最多被一条边覆盖,而选出的点要恰好被一条边覆盖。 求总共有多少合法的子图。 n,m<=20,w[i],v[i]<=108,t<=4∗108

题解

比赛的时候用meet in the middle加上搜索水了60分。其实在比赛的时候想到的离正解已经不远了,只是有一些细节没想到和因为不会证明而没有去打。 复制一波题解: 假如选出来的只有一边,那么可以直接用 hall 定理判断是否合法。但是现在选出了两 边的点,那么可以对这两边的点分别用 hall 定理判断是否合法,这是满足题目要求的必要 条件。接下来尝试证明一下这也是满足题目要求的充分条件。首先可以先把任意一组满足左 边选出子集合法的边加入。然后依次加入右边子集中的点 以及满足右边子集合法的连接 和 的边,称 是 的匹配点(加入一个点,加入一个连接它的边)。现在有三种情况: 第一种:如果 被之前加入的边覆盖,那么就丌用加边也合法。否则加入这条边,有下 面的这些情况。 第二种: 丌属于选出的子集,那么连边肯定合法。 第三种: 属于选出的子集。考虑保留当前加入的边,并删除原先覆盖 的边,设这条 边覆盖的另一个点是 。假如 丌属于选出的子集戒这是还未加入的点,肯定合法。假如 是已经加入的点,由于它匹配点肯定丌是 (因为这是 的匹配点),所以重新加入 以及覆 盖它和它匹配点的边即可。丌难发现对于 的这种情况对于每个点最多只会出现一次。 对于所有情况,都可以满足选出子集的合法性,所以选出左边的子集和右边的子集分别 满足 hall 是满足题目要求的充分条件。我们可以分别对左边和右边的点判断是否满足 hall 定理,然后就用meet in the middle统计一下方案数即可。

顺带提一波,hall定理就是若一个二分图有最大匹配,那么其充分必要条件就是左边每一个大小为k的点集必然与右边至少k个点相连。 然后判断一个子集是否满足hall定理可以用状压然后枚举其每一个子集判断是否合法,最后再判断自己是否合法即可。

代码

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define N 45#define M 1048580#define LL long longusing namespace std;int n,m,map[N][N],v[N],w[N],a1,b1,a[M],b[M],bin[N],vis[N],lim;char ch[N];bool f[M];void dfs1(int x,int sum,int now,int size,int num){ if (x>n) return; dfs1(x+1,sum,now,size,num); int p=now|bin[x-1],q=p,flag=0; while (q) { int l=q&(-q); if (!f[p-l]) { flag=1;break; } q-=l; } for (int i=1;i<=m;i++) if (map[x][i]&&!vis[i]) num++; if (!flag&&num>size) { for (int i=1;i<=m;i++) if (map[x][i]) vis[i]++; a[++a1]=min(sum+w[x],lim);f[p]=1; dfs1(x+1,min(sum+w[x],lim),p,size+1,num); for (int i=1;i<=m;i++) if (map[x][i]) vis[i]--; }}void dfs2(int x,int sum,int now,int size,int num){ if (x>m) return; dfs2(x+1,sum,now,size,num); int p=now|bin[x-1],q=p,flag=0; while (q) { int l=q&(-q); if (!f[p-l]) { flag=1;break; } q-=l; } for (int i=1;i<=n;i++) if (map[i][x]&&!vis[i]) num++; if (!flag&&num>size) { for (int i=1;i<=n;i++) if (map[i][x]) vis[i]++; b[++b1]=min(sum+v[x],lim);f[p]=1; dfs2(x+1,min(sum+v[x],lim),p,size+1,num); for (int i=1;i<=n;i++) if (map[i][x]) vis[i]--; }}void solve(){ sort(a+1,a+a1+1);sort(b+1,b+b1+1); int p1=1,p2=b1+1;LL ans=0; while (p1<=a1) { while (b[p2-1]+a[p1]>=lim&&p2>1) p2--; ans+=b1-p2+1; p1++; } PRintf("%lld",ans);}int main(){ freopen("guard.in","r",stdin);freopen("guard.out","w",stdout); bin[0]=1; for (int i=1;i<=20;i++) bin[i]=bin[i-1]*2; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",ch+1); for (int j=1;j<=m;j++) if (ch[j]=='1') map[i][j]=1; } for (int i=1;i<=n;i++) scanf("%d",&w[i]); for (int i=1;i<=m;i++) scanf("%d",&v[i]); scanf("%d",&lim); f[0]=1;a1=b1=1; dfs1(1,0,0,0,0); memset(f,0,sizeof(f)); f[0]=1; dfs2(1,0,0,0,0); solve(); return 0;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表