最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界速看：Codeforces 1630 E Making It Bipartite 题解 (Dilworth定理)

来源：博客园


(资料图片)

题目链接

首先可以想到把题目中的那张图G建出来，由于要求这张图是二分图，把它复制一遍(\(G\to G"\))，然后对于每个u，连一条无向边\(u-u"\)，这样就变成了最大独立集问题。但是一般图最大独立集是没有多项式复杂度的做法的，所以不行。

考虑先把这张图看成有向图，也就是如果\(a_i|a_j\)，就连一条有向边\(i\to j\)，令连出的图为G。由于所有\(a_i\)不相同，且\(a_i\)的大小与n一个数量级，所以这张图边数是\(O(nlogn)\)级别的。注意到这个图中如果\(i\to j,j\to k\)，那么一定有\(i\to k\)，这样就产生了三元环，不合法了。观察发现这个图合法的充要条件是：不存在同时有入边和出边的点，也就是一个点要么是入点只有入度，要么是出点只有出度。必要性显然，因为不能让长度为3的环存在；充分性：一个长度为奇数的简单环中肯定有一个同时有入度和出度的点，把这种点ban掉之后就肯定没有奇环了。

然后还是跟之前的方法一样，把图复制一遍(\(G\to G"\)，也就是拆点)，然后对于每个u，连一条有向边\(u\to u"\)，令最终的图为H。显然这个图是个DAG。这题的答案其实是这个DAG的最长反链的长度。先看求法，再说证明。

关于最长反链见Dilworth定理

根据Dilworth定理，最长反链长度=最小链覆盖的大小。注意这里的链覆盖是可以重合的，也就是一个点可以被多条链涉及。不能重合的链覆盖的求法，上面的链接里有。能重合的情况，需要先求这个图的传递闭包，也就是如果\(i\to j,j\to k\)就必须加上\(i\to k\)这条边，做完这个变换后再跟不能重合的情况一样做就行了。这题中这个图的传递闭包是很好求的，如果\(G\)中有一条边\(u\to v\)，就在H中加一条\(u\to v"\)的边，发现此时H就满足要求了，并且边数仍是\(O(nlogn)\)级别。

正确性证明：在最长反链中，\(u和u"\)显然只有最多一个被选，因为u和u"之间有一条边。令选u表示这个点没有出度(B类点)，选u"表示这个点没有入度(A类点)，都不选表示这个点被删除。我们不能接受一个点已经是A类却还有没被删除的点到它有边，或者是一个点已经是B类却还到没被删除的点有边，这也是我们唯一的要求。画一下图就会发现"选出的点两两之间没有路径"与这个要求等价。

最小链覆盖是转化成二分图匹配来跑的，Dinic跑匹配的复杂度是\(O(\sqrt n m)\)，所以总时间复杂度\(O(nlogn\sqrt n)\)。

这题一共经历了这些转化：无向图\(\to\)有向图\(\to\)不存在同时有入边和出边的点\(\to\)最长反链长度\(\to\)最小链覆盖大小\(\to\)二分图匹配

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;struct node{LL to,flow,rev;node(LL a,LL b,LL c):to(a),flow(b),rev(c){}};namespace maxFlow{LL n,dist[200010],cur[200010];vector  g[200010];queue  q;void add_edge(LL x,LL y,LL z){g[x].pb(node(y,z,g[y].size()));g[y].pb(node(x,0,g[x].size()-1));}void bfs(LL s){rep(i,n+5) dist[i]=-1;dist[s]=0;q.push(s);while(!q.empty()){int f=q.front();q.pop();rep(i,g[f].size()){if(dist[g[f][i].to]!=-1||g[f][i].flow==0) continue;dist[g[f][i].to]=dist[f]+1;q.push(g[f][i].to);}}}LL dfs(LL pos,LL t,LL flow){if(pos==t) return flow;for(int i=cur[pos];i0){g[pos][i].flow-=flow2;g[g[pos][i].to][g[pos][i].rev].flow+=flow2;return flow2;}}return 0;}LL max_flow(LL s,LL t){LL ret=0;while(true){bfs(s);if(dist[t]==-1) return ret;rep(i,n+5) cur[i]=0;while(true){LL add=dfs(s,t,1e12);if(add==0) break;ret+=add;}}}}int t,n,a[50010];vector  oe,e;int main(){  fileio();  cin>>t;  rep(tn,t)  {    scanf("%d",&n);    repn(i,n) scanf("%d",&a[i]);    oe.clear();    map  mp;    repn(i,n) mp[a[i]]=i;    repn(i,n) for(int j=a[i]+a[i];j<=50000;j+=a[i]) if(mp.find(j)!=mp.end()) oe.pb(mpr(i,mp[j]));    e.clear();    rep(i,oe.size()) e.pb(oe[i]),e.pb(mpr(oe[i].fi+n,oe[i].se+n)),e.pb(mpr(oe[i].fi,oe[i].se+n));    repn(i,n) e.pb(mpr(i,i+n));    rep(i,maxFlow::n+3) maxFlow::g[i].clear();    maxFlow::n=n*4+2;    rep(i,e.size()) maxFlow::add_edge(e[i].fi,e[i].se+n+n,1);    int ss=n*4+1,tt=n*4+2;    repn(i,n*2)    {      maxFlow::add_edge(ss,i,1);      maxFlow::add_edge(i+n*2,tt,1);    }    int ans=maxFlow::max_flow(ss,tt);    printf("%d\n",n-(n*2-ans));  }  termin();}

关键词： 传递闭包 最大独立集 就会发现