正題

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

---

題目大意

$n$個點$m$條邊的一張無向圖，每個節點有一個$w_i$表示該點需要經過奇數/偶數次。

求一條滿足條件的長度不超過$4n$的路徑

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

---

解題思路

一個結論就是一棵樹是一定有解的，出了起終點每個點有入有出，如果每個點的入和出視為點的話拿去樹上匹配，因為是聯通圖顯然能夠匹配并且一個點的入次數不會超過兒子個數*2+1次（好像是），這樣總共次數就不會超過限制。

判無解的話就是如果有兩個或以上包含奇數點的聯通塊就無解。

然后考慮怎么構造樹的方案，把思路放在局部方面，如果一個點走完兒子它不滿足條件它就需要多走一次，我們之間走到父節點然后再走回來。

此時不會影響兒子的答案并且父節點在后面還可以再進行調整。

但是根節點無法調整，不難發現我們還有一個可以使用，因為沒有限制終點一定要回到根，所以我們可以最后一次不回溯到根節點就好了

時間復雜度$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e5+10; struct node{int to,next; }a[N<<1]; int n,m,tot,w[N],ls[N],v[N]; queue<int> q;bool flag; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){v[x]=1;flag|=w[x];for(int i=ls[x];i;i=a[i].next)if(!v[a[i].to])dfs(a[i].to);return; } void solve(int x){q.push(x);w[x]^=1;v[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y])continue;solve(y);if(w[y]){q.push(x);q.push(y);w[x]^=1;}q.push(x);w[x]^=1;}return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}for(int i=1;i<=n;i++)scanf("%d",&w[i]);int cnt=0;for(int i=1;i<=n;i++){if(v[i])continue;flag=0;dfs(i);cnt+=flag;}if(cnt>1)return puts("-1")&0;memset(v,0,sizeof(v));for(int i=1;i<=n;i++){if(!w[i])continue;solve(i);int l=q.size();if(w[i])l--;printf("%d\n",l);while(l){printf("%d ",q.front());l--;q.pop();}return 0;}printf("0\n");return 0; }

總結

以上是生活随笔為你收集整理的CF453C-Little Pony and Summer Sun Celebration【构造】的全部內容，希望文章能夠幫你解決所遇到的問題。

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