BZOJ4116 [WF2015] Tours.md

BZOJ4116 [WF2015] Tours

题目链接

Solution

结论零：首先可以发现一个相当显然的结论， $k|Gcd_{i=1}^{|H|}(H_i)$

其中 $H$ 为图中所有简单环大小的集合。

然后因为可能有边会出现在不只一个简单环中，所以这个上界是不一定满足的。

正确的做法如下。

结论一：我们考虑把所有的边划分为若干个极大的集合，

满足每一个简单环都能恰好被其中若干个集合的并恰好表示。

答案为所有的集合的大小的 $gcd$ 。

如何划分集合呢？

结论二：我们把每条边删除，图中所有新增的环都应当和它划分到一个集合。

于是我们可以 $O(m^2)$ 地得到答案。

网上好像找不到证明，于是自己证了一下。

我们先证明第二个结论，及划分出的极大集合可以通过删边找新增桥的方法完成。

我们可以较容易地发现，新增的桥是和删除的这条边出现且仅出现在相同的简单环里的边。

为了方便表述，我们设删除的这条边为 $e$ ，包含 $e$ 的所有简单环的集合为 $H$ ，上述新增的桥边集合为 $E$

显然，我们把这些边划分在一个集合中对于合并 $H$ 时是满足的，对于合并其他环时是没有影响的。所以这样的划分是可行的。

其次我们来证明它是极大的。如果不是极大的，那么必定该集合中有一条边 $e'$ 至少出现在 $H$ 之外的一个简单环 $h'$ 中，那么合并那个环的时候，必定会用到 $e'$ 这条边，此时会附带用上这个集合中的其他所有边，就会出现不在 $h'$ 中的边，这样是不符合集合要求满足的性质的。

故上述做法能够得到合法且极大的集合表示

然后我们再来证明第一个结论。

首先我们发现第一个结论也是满足我们发现的结论零的。因为 $gcd(a,b)|a+b$

其实这个结论也就是结论零的强化版。我们发现结论一其实就是把和出现在同一些简单环中同时也出现在一些不同的简单环中的边分开了。

我们发现这样分开显然是对的，我们只需要对每一个集合都满足，最后由于每一个简单环都是若干个的并，所以每一个简单环一定满足。

现在我们要证明它是极大的，也就是证明更大的一定是不满足的。

我们发现，所谓更大，就是出现集合之间通过互补来满足简单环的要求的。

显然，这样的互补情况要出现，至少要有三个互补。

我们不妨考虑这样三个集合 $A,B,C$

他们出现的所有简单环集合分别是 $A',B',C',A'\cap B'\neq\empty, B'\cap C'\neq\empty$

我们考虑如果通过互补来完成也就是说对于所有 $A'\cap B'$ 要满足条件， $A'$ 多出来的与 $B'$ 中缺少的相同，

同样的对于 $B' \cap C'$ 也会得到 $C'$ 中多出来的与 $B'$ 中缺少的相同，也就是说 $A'$ 中和 $C'$ 中多出来的颜色是相同的。

考察 $B$ 中的边集，我们不难发现， $A'\cap C'\neq\empty$ 所以对于 $A'\cap C'$ ，就多出了两倍 $B'$ 缺少的颜色，所以不满足。

于是，不存在这样互补的情况。

综上，我们证明了划分集合的方法是极大且可行的。

Hints

无

Code

 
xxxxxxxxxx
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
  
const int maxn = 2010;
struct edge {
    int to , nxt;
    edge(){}
    edge(int nxt , int to) : to(to) , nxt(nxt){}
}e[maxn << 1];
int n , m , last[maxn] , cnt = 1;
  
inline void insert(int u , int v) {e[++cnt] = edge(last[u] , v); last[u] = cnt;}
inline void addedge(int u , int v) {insert(u , v); insert(v , u);}
 
int dfn[maxn] , low[maxn] , ind = 0 , ans = 0;
bool vis[maxn << 1] , inset[maxn << 1] , bridge[maxn << 1] , isbridge[maxn << 1];
 
inline void dfs(int x , int fa)
{
    dfn[x] = low[x] = ++ ind;
    for(int i = last[x]; i; i = e[i].nxt)
    {
        if(vis[i] || e[i].to == fa) continue;
        int v = e[i].to;
        if(!dfn[v])
        {
            dfs(v , x);
            low[x] = min(low[x] , low[v]);
            if(low[v] > dfn[x]) isbridge[i] = 1;
        }
        else low[x] = min(low[x] , dfn[v]);
    }
}
 
inline void Solve(int x)
{
    vis[x] = vis[x ^ 1] = 1;
    memset(isbridge , 0 , sizeof(isbridge));
    memset(dfn , 0 , sizeof(dfn));
    memset(low , 0 , sizeof(low));
    ind = 0; int tot = 1;
    for(int i = 1; i <= n; i ++)
        if(!dfn[i]) dfs(i , 0);
    for(int i = 2; i <= cnt; i += 2)
    {
        if(bridge[i] || bridge[i ^ 1]) continue;
        if(isbridge[i] || isbridge[i ^ 1]) ++ tot , inset[i] = inset[i ^ 1] = 1;
    }
    ans = __gcd(ans , tot);
     
    vis[x] = vis[x ^ 1] = 0;
}
 
int main()
{
//  freopen("tours.in","r",stdin);
    n = read() , m = read();
    for(int i = 1; i <= m; i ++)
    {
        int u = read() , v = read();
        addedge(u , v);
    }
    for(int i = 1; i <= n; i ++)
        if(!dfn[i]) dfs(i , 0);
    for(int i = 2; i <= cnt; i ++) bridge[i] = isbridge[i];
    for(int i = 2; i <= cnt; i += 2)
    {
        if(inset[i] || bridge[i] || bridge[i ^ 1]) continue;
        Solve(i); 
    }
     
    for(int i = 1; i <= ans; i ++)
        if(ans % i == 0) printf("%d",i),putchar(i==ans?'\n':' ');
     
    return 0;
}