正題

題目鏈接:https://loj.ac/p/3077

---

題目大意

給出$n$個點$m$條邊的一張簡單無向圖，求是否存在兩個長度相等的簡單環(huán)。

$1\le n\le 10^4,1\le m\le 10^6$

---

解題思路

先考慮一個暴力的做法，我們暴力搜索圖上的所有環(huán)，記$c_i$表示長度為$i$的環(huán)的個數(shù)。

那么注意到一個長度為$x$的環(huán)，我們會重復統(tǒng)計$2x$次（一輪和翻轉后的一輪），所以如果$c_x>2x$那么就可以輸出$Yes$了。

根據(jù)鴿籠原理，我們能注意到圖上的環(huán)的總數(shù)不能超過$n?2$（長度為$3～n$的各一個），否則答案一定是$Yes$。然后考慮在一棵樹上，我們每加入一條邊后至少增加一個環(huán)，所以如果$m\ge 2n?3$的話答案一定是$Yes$，這樣我們就成功讓$m$就和$n$同級了。

然后考慮如果我們走的每一步都能保證往后是能搜出至少一個環(huán)的話，那么一個環(huán)最多被統(tǒng)計$2x$次，也就是要搜$2x^2$個點，那么如果答案是$No$我們就最多只需要搜${\sum }_{i=1}^{n}2i^2$也就是$O(n^3)$級別次。

那么如何保證我們走的每個點一定能搜出環(huán)，很簡單，假設我們的環(huán)從$s$出發(fā)，我們走到一個點是時暴力$O(n)$地判斷它是否能不經(jīng)過目前重復的走到$s$，如果能那么它搜下去至少會有一個新的環(huán)。

這樣我們就做到$O(n^4)$的復雜度了。

然后是一個神仙優(yōu)化

我們假設我們在圖上刪除$\sqrt{n}$條邊，那么每條邊被刪除的概率就是$\frac{1}{\sqrt{n}}$，假設圖恰好長度為$3～n$的環(huán)各有一個，那么一個長度為$x$的環(huán)沒被刪除的概率就是$(1?\frac{1}{\sqrt{n}}{)}^x$，同理那最后圖上剩下的環(huán)的期望個數(shù)就是
$$\sum _{i=3}^n{\left(1?\frac{1}{\sqrt{n}}\right)}^i<\frac{1}{1?\left(1?\frac{1}{\sqrt{n}}\right)}=\sqrt{n}$$
所以刪除$\sqrt{n}$條邊之后圖上期望剩下$\sqrt{n}$個環(huán)，因為是隨機刪的，所以如果按照最優(yōu)去刪除的話肯定存在一種方案使得圖上剩下不超過$\sqrt{n}$個環(huán)。

然后我們指定刪一條邊肯定能刪掉一個環(huán)，所以我們只需要刪除$2\sqrt{n}$條邊就可以使得圖上不存在任何一個環(huán)，換句話說我只需要刪除$2\sqrt{n}$條邊就可以讓這張圖的邊數(shù)不超過$n?1$，所以這張圖的邊數(shù)不超過$n?1+2\sqrt{n}$。

所以再換句話說，我們就得到了最重要的結論，如果圖的邊數(shù)大于等于$n+2\sqrt{n}$那么答案肯定是$Yes$。

所以我們只需要考慮怎么處理$n+2\sqrt{n}$的情況，我們先找出一棵生成樹，然后對于所有的非樹邊的端點建出一棵虛樹，然后連接上非樹邊，這樣我們就得到一張邊數(shù)和點數(shù)都是$\sqrt{n}$級別的圖。

不難發(fā)現(xiàn)我們上面那種情況也是能處理帶權圖的（需要注意的是一個長度為$x$的環(huán)出現(xiàn)的次數(shù)不是$2x$了，我們需要記錄這個環(huán)在虛樹上的邊數(shù)$s$，如果存在兩種不同的邊數(shù)肯定是兩個不同的環(huán)，否則就判斷出現(xiàn)次數(shù)$>2s$），所以我們的復雜度就到了快速的$O(n^2)$了。

因為跑不滿并且這是LOJ所以能過。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cmath> using namespace std; const int N=1e4+10; struct node{int to,next,w; }a[N<<1]; int n,m,tot,cnt,ls[N],dep[N],pos[N]; int las[N],vis[N],dis[N],len[N],c[N]; vector<int> G[N]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=w;return; } void dfs(int x,int fa){dep[x]=dep[fa]+1;las[x]=fa;int num=0;for(int i=0;i<G[x].size();i++){int y=G[x][i];if(y==fa)continue;if(dep[y]){if(dep[y]>dep[x])continue;if(!pos[x])pos[x]=x;if(!pos[y])pos[y]=y;addl(pos[x],pos[y],1);}else{dfs(y,x);if(pos[y])num=num?-1:pos[y];}}if(!pos[x]&&num<0)pos[x]=x;if(pos[x]){for(int i=0;i<G[x].size();i++){int y=G[x][i];if(y==fa)continue;if(pos[y]&&las[y]==x)addl(pos[x],pos[y],dep[pos[y]]-dep[pos[x]]);}}else pos[x]=num;return; } bool calc(int x,int fa,int t){if(!dep[x])return 1;vis[x]=t;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(i==fa||dep[y]>0||vis[y]==t)continue;bool flag=calc(y,i^1,t);if(flag)return 1;}return 0; } void solve(int x,int fa){if(!calc(x,fa,++cnt))return;for(int i=ls[x];i;i=a[i].next){int y=a[i].to,r=dis[x]+a[i].w;if(i==fa)continue;if(!dep[y]){if(!len[r])len[r]=dep[x]+1;if(len[r]!=dep[x]+1){puts("Yes");exit(0);}c[r]++;if(c[r]>len[r]*2){puts("Yes");exit(0);}}if(dep[y]>=0)continue;dep[y]=dep[x]+1;dis[y]=dis[x]+a[i].w;solve(y,i^1);dep[y]=-1;}return; } int main() { // freopen("4-01.in","r",stdin);scanf("%d%d",&n,&m);tot=1;if(m>n+sqrt(n)*2.0)return puts("Yes")&0;for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}for(int i=1;i<=n;i++)if(!dep[i])dfs(i,0);memset(dep,-1,sizeof(dep));for(int i=1;i<=n;i++)if(pos[i]==i)dep[i]=0,dis[i]=0,solve(i,0),dep[i]=-1;puts("No");return 0; }

總結

以上是生活随笔為你收集整理的Loj#3077-「2019 集训队互测 Day 4」绝目编诗【结论,虚树,鸽笼原理】的全部內容，希望文章能夠幫你解決所遇到的問題。

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