二分图，点有点权。 选择一个点集，使得存在原图的一个匹配可以包含该点集所有点，并使点集中点权和超过给定T，求方案数。
虽然不会证，但是X集合中可被覆盖的点集和Y集合中可被覆盖的点集拼成的点集也是能被覆盖的！ 然后就搜搜搜！
#include<cstdio>#include<algorithm>#define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;typedef long long ll;const int maxn=20+10,maxtot=1048576+10;int w[maxn],v[maxn],a[maxn],b[maxn];ll sum[maxtot];bool dis[maxn][maxn],bz[maxn],fl[maxn],lf[maxn];int i,j,k,l,t,n,m,num,tot;ll ans;char get(){ char ch=getchar(); while (ch!='0'&&ch!='1') ch=getchar(); return ch;}bool pd(int x){ int i; fo(i,1,n) if (!bz[i]&&dis[i][x]){ bz[i]=1; if (!a[i]||pd(a[i])){ b[x]=i; a[i]=x; return 1; } } return 0;}void dfs(int x,ll y){ if (x==m+1){ sum[++tot]=y; return; } dfs(x+1,y); int i; fo(i,1,n) bz[i]=0; if (pd(x)){ dfs(x+1,y+v[x]); a[b[x]]=0; b[x]=0; }}bool dp(int x){ int i; fo(i,1,m) if (!bz[i]&&dis[x][i]){ bz[i]=1; if (!b[i]||dp(b[i])){ a[x]=i; b[i]=x; return 1; } } return 0;}void dg(int x,ll y){ if (x==n+1){ int l=1,r=tot+1,mid; while (l<r){ mid=(l+r)/2; if (y+sum[mid]>=num) r=mid;else l=mid+1; } ans+=(ll)(tot-l+1); return; } dg(x+1,y); int i; fo(i,1,m) bz[i]=0; if (dp(x)){ dg(x+1,y+w[x]); b[a[x]]=0; a[x]=0; }}bool pdd(int x){ int i; fo(i,1,n) if (!bz[i]&&dis[i][x]){ bz[i]=1; if (!a[i]||pdd(a[i])){ b[x]=i; a[i]=x; return 1; } } return 0;}bool dpp(int x){ int i; fo(i,1,m) if (!bz[i]&&dis[x][i]){ bz[i]=1; if (!b[i]||!fl[b[i]]||dpp(b[i])){ if (b[i]&&!fl[b[i]]) a[b[i]]=0; a[x]=i; b[i]=x; return 1; } } return 0;}void dgg(int x,ll y){ int i,aa[maxn],bb[maxn]; if (x==n+1){ if (y>=num) ans++; return; } dgg(x+1,y); bool czy=0; fo(i,1,m) bz[i]=0; fo(i,1,n) aa[i]=a[i]; fo(i,1,m) bb[i]=b[i]; if (a[x]||dpp(x)){ fl[x]=1; dgg(x+1,y+w[x]); fl[x]=0; } fo(i,1,n) a[i]=aa[i]; fo(i,1,m) b[i]=bb[i];}void dfss(int x,ll y){ int i,aa[maxn],bb[maxn]; if (x==m+1){ fo(i,1,n) aa[i]=a[i]; fo(i,1,m) bb[i]=b[i]; dgg(1,y); fo(i,1,n) a[i]=aa[i]; fo(i,1,m) b[i]=bb[i]; return; } dfss(x+1,y); fo(i,1,n) bz[i]=0; fo(i,1,n) aa[i]=a[i]; fo(i,1,m) bb[i]=b[i]; if (pdd(x)){ lf[x]=1; dfss(x+1,y+v[x]); lf[x]=0; } fo(i,1,n) a[i]=aa[i]; fo(i,1,m) b[i]=bb[i];}void brute(){ dfss(1,0); PRintf("%lld/n",ans);}int main(){ freopen("guard.in","r",stdin);freopen("guard.out","w",stdout); scanf("%d%d",&n,&m); fo(i,1,n){ fo(j,1,m) if (get()=='1') dis[i][j]=1; } fo(i,1,n) scanf("%d",&w[i]); fo(i,1,m) scanf("%d",&v[i]); scanf("%d",&num); if (n<=8&&m<=8){ brute(); return 0; } dfs(1,0); sort(sum+1,sum+tot+1); dg(1,0); printf("%lld/n",ans);}新闻热点
疑难解答
