正題

題目鏈接:https://codeforces.com/gym/103049/problem/J

---

題目大意

$n$個點$m$條邊的一張無向圖，選出一條路徑后去掉路徑上的點，然后將剩下的點分成點數相等的兩份使得兩份之間沒有邊連接。

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

---

解題思路

先跑出$dfs$樹，這樣就保證了所有的非樹邊都是返祖邊。

發現如果我們選出樹上一條根節點出發的路徑那么其他子樹之間一定是不連通的（因為要么子樹之間有環，要么往上的環被刪除）。

所以問題就變成了選出一條從根出發的路徑然后把其他的分成大小相等的兩份。

考慮貪心解決，我們走到一個點時可以把兒子的子樹大小從小到大排列，然后兩邊那邊不夠就加給哪邊，加剩最大的一個再繼續往下分。

因為這樣分的差一定不大于最大的那個，所以肯定是對的。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=2e5+10; int n,m,siz[N],mark[N]; vector<int> G[N],T[N],p; void dfs(int x,int fa){siz[x]=1;for(int i=0;i<G[x].size();i++){int y=G[x][i];if(y==fa||siz[y])continue;T[x].push_back(y);dfs(y,x);siz[x]+=siz[y];}return; } bool cmp(int x,int y) {return siz[x]>siz[y];} void calc(int x,int fa,int a,int b){sort(T[x].begin(),T[x].end(),cmp);p.push_back(x);int lr=0;for(int i=0;i<T[x].size();i++){int y=T[x][i];if(y==fa)continue;if(!lr)lr=y;else if(a<=b)a+=siz[y],mark[y]=1;else b+=siz[y],mark[y]=2;}if(a<=b&&a+siz[lr]==b){mark[lr]=1;return;}if(a>=b&&b+siz[lr]==a){mark[lr]=2;return;}calc(lr,x,a,b);return; } void print(int x,int fa,int z){if(!mark[x])mark[x]=mark[fa];for(int i=0;i<T[x].size();i++)if(T[x][i]!=fa)print(T[x][i],x,z);if(mark[x]==z)printf("%d ",x);return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}dfs(1,0);calc(1,1,0,0);int w=(n-p.size())/2;printf("%d %d\n",p.size(),w);for(int i=0;i<p.size();i++)printf("%d ",p[i]);mark[0]=0;putchar('\n');print(1,0,1);putchar('\n');print(1,0,2);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的NWERC2020J-Joint Excavation【构造,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

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