正題

題目鏈接:https://www.luogu.com.cn/problem/P7516

---

題目大意

懶了，直接抄題意了
對于一張 $n$ 個(gè)點(diǎn) $m$ 條邊的有向圖 $G$（頂點(diǎn)從 $1～n$ 編號(hào)），定義函數(shù) $f(u,G)$：

初始化返回值 $cnt=0$，圖 $G^{\prime }=G$。

從 $1$ 至 $n$ 按順序枚舉頂點(diǎn) $v$，如果當(dāng)前的圖 $G^{\prime };$ 中，從 $u$ 到 $v$ 與從 $v$ 到 $u$ 的路徑都存在，則將 $cnt+1$，并在圖 $G^{\prime };$ 中刪去頂點(diǎn) $v$ 以及與它相關(guān)的邊。

第 $2$ 步結(jié)束后，返回值 $cnt$ 即為函數(shù)值。

現(xiàn)在給定一張有向圖 $G$，請你求出 $h(G)=f(1,G)+f(2,G)+?+f(n,G)$ 的值。

更進(jìn)一步地，記刪除（按輸入順序給出的）第 $1$ 到 $i$ 條邊后的圖為 $G_i$（$1\le i\le m$），請你求出所有 $h(G_i)$ 的值。

$1\le n\le 10^3,1\le m\le 2\times 10^5$

---

解題思路

但凡一個(gè)不按慣性思維思考的方法都可以做出這道題

這個(gè)刪邊就很意義不明，反過來直接改成加邊就簡單很多。

然后還有一個(gè)問題就是是否刪點(diǎn)的判斷也是沒有必要的：

假設(shè)對于起點(diǎn)$u$能走到$v$，$v$不能走到$u$，那么顯然并不存在一個(gè)節(jié)點(diǎn)$x$使得$u$能走到$x$且$x$能走到$u$并且$v$是這些路徑的必經(jīng)點(diǎn)，因?yàn)槟敲?span id="ze8trgl8bvbq" class="katex--inline">$v$肯定在這個(gè)環(huán)上，那么$v$顯然能走到$u$。

所以現(xiàn)在$f(u,G)$能否統(tǒng)計(jì)$v$就變?yōu)榱伺袛嗍欠翊嬖谝粋€(gè)$u\to v\to u$的環(huán)使得路徑上的所有點(diǎn)編號(hào)不小于$min(u,v)$。

那么不妨考慮一下兩個(gè)點(diǎn)對$(u,v)$之間不斷加邊之后第一次產(chǎn)生貢獻(xiàn)的時(shí)間，每條邊的權(quán)值設(shè)為加入的時(shí)間，這個(gè)時(shí)間就是$u\to v\to u$的一條不經(jīng)過編號(hào)小于$min(u,v)$點(diǎn)的情況下最大權(quán)值最小的路徑。

這樣Flody就有$O(n^3)$的算法了。

然后我們想了很久感覺最短路行不通，那么此時(shí)就需要摒棄慣性思維的想法了，我們考慮另一個(gè)更暴力的做法，我們每次加邊然后暴力判斷每個(gè)點(diǎn)之間的聯(lián)通，發(fā)現(xiàn)這樣的時(shí)間復(fù)雜度是$O(n{m}^2)$的。

然后依舊的我們考慮另一種可能，我們最外層不枚舉加邊，而是枚舉需要統(tǒng)計(jì)答案的起點(diǎn)$u$，然后每次加一條邊$(x,y)$，如果$u$能走到$x$且不能走到$y$那么此時(shí)$u$能走到$y$了，從$y$開始$bfs$所有其他沒有走過的節(jié)點(diǎn)，需要注意的是走過的邊兩邊都是遍歷過的所以可以直接刪除。

這樣的時(shí)間復(fù)雜度就是$O(n(n+m))$，可以通過本題。

需要卡常

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N=1e3+10,M=2e5+10; struct node{int to,next; }a[M]; int n,m,f[N][N],g[N][N]; int ex[M],ey[M],ans[M]; vector<int> G[N],D[N];queue<int> q; void bfs(int x,int s,int w){q.push(x);while(!q.empty()){int x=q.front();q.pop();f[s][x]=w;for(int i=0;i<G[x].size();i++)if(!f[s][G[x][i]])q.push(G[x][i]);G[x].clear();}return; } void bgs(int x,int s,int w){q.push(x);while(!q.empty()){int x=q.front();q.pop();g[s][x]=w;for(int i=0;i<D[x].size();i++)if(!g[s][D[x][i]])q.push(D[x][i]);D[x].clear();}return; } int main() {scanf("%d%d",&n,&m);m++;for(int i=2;i<=m;i++)scanf("%d%d",&ex[i],&ey[i]);reverse(ex+2,ex+1+m);reverse(ey+2,ey+1+m);for(int x=1;x<=n;x++){for(int i=1;i<=n;i++)G[i].clear();for(int i=1;i<=n;i++)D[i].clear();f[x][x]=g[x][x]=1;for(int i=2;i<=m;i++){if(ex[i]<x||ey[i]<x)continue;if(f[x][ex[i]]&&!f[x][ey[i]])bfs(ey[i],x,i);else if(!f[x][ex[i]]&&!f[x][ey[i]])G[ex[i]].push_back(ey[i]);if(g[x][ey[i]]&&!g[x][ex[i]])bgs(ex[i],x,i);else if(!g[x][ey[i]]&&!g[x][ex[i]])D[ey[i]].push_back(ex[i]);}}for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(f[i][j]&&g[i][j])ans[max(f[i][j],g[i][j])]++;for(int i=1;i<=m;i++)ans[i]+=ans[i-1];reverse(ans+1,ans+1+m);for(int i=1;i<=m;i++)printf("%d ",ans[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P7516-[省选联考2021A/B卷]图函数【bfs】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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