CF1651E
CF1651E Sum of Matchings
\(\text{Description}\)
定义一张图 \(G\) 的最大匹配当中的边数是 \(MM(G)\)。
给你一张二分图，左部节点编号 \(1 \sim n\)，右部节点编号 \(n+1 \sim 2n\)，保证每个节点的度数必然为 \(2\)。
设 \(G(l,r,L,R)\) 表示左部节点编号在 \([l,r]\)，右部节点编号在 \([L,R]\) 之间的节点和他们相关的边组成的导出子图。
求 \(\sum MM(G(l,r,L,R))\)，保证 \(2\le n\le 1500\)。
\(\text{Solution}\)
考虑整张图的形态，因为是二分图（不含奇环），且每个节点的度数必然是 \(2\)。
那么这张图必然全部由一些简单环组成，且这些简单环都是偶环。
考虑一个偶环 \(R\) 如果被包含在一个导出子图 \(G\prime\) 当中，他能对 \(MM(G\prime)\)做的贡献是什么。
显然是 \(\lceil\dfrac{edge}{2}\rceil\)，\(edge\) 是这个偶环 \(R\) 包含的边数，这个用类似匈牙利算法的思想即可得到。
那么这个偶环 \(R\) 必然会被一堆子图所包含，设这样的子图数量是 \(cnt\)，那么他对答案的贡献就是 \(\lceil\dfrac{edge}{2}\rceil\times cnt\)。
\(cnt\) 也比较好算，记录偶环上属于左部和右部分别的节点编号最大最小值 \(Lmax,Lmin,Rmax,Rmin\)
（右部的算完之后要减去 \(n\)）。
那 \(cnt\) 就应该是：\(Lmin\times(n-Lmax+1)\times Rmin\times(n-Rmax+1)\)。
就是乘法原理。
但是还要考虑另外的一种情况，如果被这个子图包含的不是这个偶环，而是这个偶环上的一条链 \((u,v)\)。
那么这条链 \((u,v)\) 对于每一个包含它的子图的 \(MM\) 的贡献必然仍旧是 \(\lceil\dfrac{edge}{2}\rceil\)，\(edge\) 是这条链 \((u,v)\) 包含的边数。
还是需要计算他被多少个子图包含，并记录链上左部和右部分别的节点编号最大最小值 \(Lmax,Lmin,Rmax,Rmin\) （右部的算完之后还是要减去 \(n\)）。
但是这个时候链上的节点编号就不一定是连续的了，需要去掉偶环当中不在这个链上的节点。
那么对于偶环 \(R\) 去掉这个链 \((u,v)\) 之后的到的链 \(R-(u,v)\) 再记录它的 \(Lmax,Lmin,Rmax,Rmin\) 就可以了。
\(\text{Code}\)
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 | #include<bits/stdc++.h>
using namespace std;
using i64=long long;
constexpr int si=3e3+10,inf=0x3f3f3f3f;
int n,vis[si];
i64 a[si],cur,ans=0;
std::vector<int>G[si];
inline int d(int x){ return x<<1; }
inline void dfs(int u){ a[cur++]=u,vis[u]=1; for(auto v:G[u]) if(!vis[v]) dfs(v); }
inline void add(int u,int v){ G[u].push_back(v);G[v].push_back(u); }
int main(){
cin>>n; for(register int i=1,u,v;i<=d(n);++i) cin>>u>>v,add(u,v);
for(register int i=1;i<=d(n);++i){
if(!G[i].size() || vis[i]) continue;
cur=0,dfs(i); i64 Lmin=inf,Rmin=inf,Lmax=0,Rmax=0;
// 偶环的情况
for(register int j=0;j<cur;++j){
if(a[j]<=n) Lmin=min(Lmin,a[j]),Lmax=max(Lmax,a[j]);
else Rmin=min(Rmin,a[j]-n),Rmax=max(Rmax,a[j]-n);
} i64 cnt=Lmin*(n-Lmax+1)*Rmin*(n-Rmax+1); ans+=cnt*(cur/2);
// 偶环上的链的情况
for(register int u=0;u<cur;++u){
i64 Lmin=inf,Rmin=inf,Lmax=0,Rmax=0;
if(a[u]<=n) Lmin=min(Lmin,a[u]),Lmax=max(Lmax,a[u]);
else Rmin=min(Rmin,a[u]-n),Rmax=max(Rmax,a[u]-n);
int pos=(u+1)%cur,edge_cnt=0; while(pos!=u){ edge_cnt++;
if(a[pos]<=n) Lmin=min(Lmin,a[pos]),Lmax=max(Lmax,a[pos]);
else Rmin=min(Rmin,a[pos]-n),Rmax=max(Rmax,a[pos]-n);
int Prev=(u-1+cur)%cur,ff=true; i64 O_Lmin=0,O_Rmin=0,O_Lmax=n+1,O_Rmax=n+1;
if(a[Prev]<=n){
if(a[Prev]<Lmin) O_Lmin=max(O_Lmin,a[Prev]);
else if(a[Prev]>Lmax) O_Lmax=min(O_Lmax,a[Prev]);
else ff=false;
}
else{
if(a[Prev]-n<Rmin) O_Rmin=max(O_Rmin,a[Prev]-n);
else if(a[Prev]-n>Rmax) O_Rmax=min(O_Rmax,a[Prev]-n);
else ff=false;
} Prev=(pos+1)%cur;
if(a[Prev]<=n){
if(a[Prev]<Lmin) O_Lmin=max(O_Lmin,a[Prev]);
else if(a[Prev]>Lmax) O_Lmax=min(O_Lmax,a[Prev]);
else ff=false;
}
else{
if(a[Prev]-n<Rmin) O_Rmin=max(O_Rmin,a[Prev]-n);
else if(a[Prev]-n>Rmax) O_Rmax=min(O_Rmax,a[Prev]-n);
else ff=false;
} if(ff) ans+=(Lmin-O_Lmin)*(O_Lmax-Lmax)*(Rmin-O_Rmin)*(O_Rmax-Rmax)*((edge_cnt+1)/2); pos=(pos +1)%cur;
}
}
} cout<<ans<<endl; return 0;
}
|
最后更新:
May 9, 2023