Codeforces 1630 E Making It Bipartite 题解 (Dilworth定理)
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
首先可以想到把题目中的那张图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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void 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 <node> g[200010];
queue <LL> 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];i<g[pos].size();++i,++cur[pos])
{
if(g[pos][i].flow==0||dist[g[pos][i].to]!=dist[pos]+1) continue;
LL flow2=dfs(g[pos][i].to,t,min(flow,g[pos][i].flow));
if(flow2>0)
{
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 <pii> oe,e;
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
scanf("%d",&n);
repn(i,n) scanf("%d",&a[i]);
oe.clear();
map <int,int> 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();
}
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |