2019.1.9交流題，現在看還是不會，，，

如果只有一邊，那么Hall定理即可。

兩邊？分別滿足Hall定理，就是合法的！

證明（構造方案）：

左集合先任意形成一個合法匹配，單點增量加入右集合和與右集合有關的邊進行調整

加入bj，枚舉連接bj的邊，連向ai

直接大力匈牙利匹配即可。由于Hall定理成立，所過之處一定能返回true

DP之后雙指針即可。

注意，左、右是空集合也合法

#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);} template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Modulo{ const int mod=998244353; int ad(int x,int y){return (x+y)>=mod?x+y-mod:x+y;} void inc(int &x,int y){x=ad(x,y);} int mul(int x,int y){return (ll)x*y%mod;} void inc2(int &x,int y){x=mul(x,y);} int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;} template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);} template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);} } // using namespace Modulo; namespace Miracle{ const int N=21; int sz[1<<N]; int lim; struct SET{int n;int go[N];int val[N];int f[1<<N];int s[1<<N]; int ok[1<<N],cnt;void in(){for(reg i=0;i<n;++i) rd(val[i]);}void dp(){// cout<<"D-------P "<<endl;f[0]=1;for(reg i=0;i<(1<<n);++i){int to=0;for(reg j=0;j<n;++j){if((i>>j)&1) {to|=go[j];s[i]+=val[j];}}f[i]=(sz[to]>=sz[i]);if(f[i]){for(reg j=0;j<n;++j){if((i>>j)&1) f[i]&=f[i^(1<<j)];}}if(f[i]){// cout<<" OK "<<i<<" s "<<s[i]<<endl;ok[++cnt]=s[i];}}sort(ok+1,ok+cnt+1);} }le,ri; char s[N]; int main(){rd(le.n);rd(ri.n);int up=max(le.n,ri.n)+1;for(reg i=0;i<le.n;++i){scanf("%s",s);for(reg j=0;j<ri.n;++j){if(s[j]=='1') le.go[i]|=(1<<j),ri.go[j]|=(1<<i);}}le.in();ri.in();rd(lim);for(reg i=1;i<(1<<up);++i){sz[i]=sz[i>>1]+(i&1);}le.dp();ri.dp();// cout<<le.cnt<<" "<<ri.cnt<<endl;ll ans=0;int ptr=ri.cnt;for(reg i=1;i<=le.cnt;++i){while(ptr&&le.ok[i]+ri.ok[ptr]>=lim) --ptr;// ptr=lower_bound(ri.ok+1,ri.ok+ri.cnt+1,lim-le.ok[i])-ri.ok-1;ans+=ri.cnt-ptr;}cout<<ans;return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle* */

?

轉載于:https://www.cnblogs.com/Miracevin/p/11002512.html

總結

以上是生活随笔為你收集整理的bzoj4788: [CERC2016]Bipartite Blanket的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。