題目鏈接

https://atcoder.jp/contests/agc004/tasks/agc004_f

題解

神仙題。。

首先考慮樹的情況，樹是二分圖，因此假設(shè)我們對(duì)二分圖進(jìn)行黑白染色，那么操作就變成了，每次選擇兩個(gè)不同色的點(diǎn)來取反。然后再把黑色視作標(biāo)記，那么問題就變成了，初始一些點(diǎn)上有標(biāo)記，每次可以把標(biāo)記沿著邊移動(dòng)到一個(gè)沒標(biāo)記的點(diǎn)，要把標(biāo)記全部移動(dòng)到和原來不同的位置上，求最小代價(jià)！
然后這個(gè)問題的做法就是，首先如果兩種顏色個(gè)數(shù)不同就無解，否則考慮一個(gè)下界，對(duì)于每一條邊而言，它至少要運(yùn)送標(biāo)記的次數(shù)等于其一端子樹內(nèi)黑白點(diǎn)個(gè)數(shù)差的絕對(duì)值。對(duì)所有的邊求和就是答案的下界，而我們也能構(gòu)造出來一種達(dá)到這個(gè)下界的方案，構(gòu)造詳見官方題解。

然后考慮基環(huán)樹。當(dāng)環(huán)是奇環(huán)和偶環(huán)時(shí)，其作用不同，因此需要分類討論。

當(dāng)環(huán)是偶環(huán)時(shí)，非樹邊的作用是多了一條運(yùn)送標(biāo)記的邊。假設(shè)這條邊運(yùn)送了\(x\)個(gè)標(biāo)記（可正可負(fù)），那么其所影響的是環(huán)上的點(diǎn)，需要最小化的是一個(gè)\(\sum |x-a_i|\)的形式，直接取中位數(shù)即可。

當(dāng)環(huán)是奇環(huán)時(shí)，非樹邊的作用是可以給兩個(gè)端點(diǎn)的標(biāo)記同時(shí)\(+1\)或\(-1\). 顯然\(+1\)和\(-1\)都出現(xiàn)是不優(yōu)的，由于操作可逆可以假設(shè)是\(+1\) (否則交換初始狀態(tài)和終止?fàn)顟B(tài))。在這種情況下，若兩種顏色個(gè)數(shù)奇偶性不同就無解，否則執(zhí)行這種操作的次數(shù)\(x\)是確定的（因?yàn)槌跏己徒K止時(shí)兩種顏色點(diǎn)數(shù)確定）。那么就可以認(rèn)為給這兩個(gè)端點(diǎn)分別加了\(x\)個(gè)標(biāo)記，然后再執(zhí)行樹的算法即可。

時(shí)間復(fù)雜度\(O(N)\)或\(O(N\log N)\).

代碼

#include<bits/stdc++.h> #define llong long long using namespace std;const int N = 1e5; struct Edge {int nxt,v; } e[(N<<1)+3]; int fe[N+3]; int fa[N+3]; bool vis[N+3]; int dep[N+3]; int a[N+3]; int s[N+3]; vector<int> vec; int n,m,en,au,av,sum; llong ans;int absl(int x) {return x<0?-x:x;}void addedge(int u,int v) {en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en; }void dfs(int u,int prv) {a[u] = dep[u]&1?-1:1; sum += a[u]; s[u] = a[u];vis[u] = true;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(v==prv) continue;if(vis[v]){au = u,av = v;}else{dep[v] = dep[u]+1;fa[v] = u;dfs(v,u);s[u] += s[v];}} }void dfs2(int u,int prv) {s[u] = a[u];vis[u] = true;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(v==prv) continue;if(vis[v]){au = u,av = v;}else{dep[v] = dep[u]+1;dfs2(v,u);s[u] += s[v];}} }int main() {scanf("%d%d",&n,&m);for(int i=1; i<=m; i++){int u,v; scanf("%d%d",&u,&v);addedge(u,v); addedge(v,u);}sum = 0; dep[1] = 0; dfs(1,0);if(m==n-1){if(sum) {puts("-1");}else{ans = 0ll;for(int i=1; i<=n; i++){ans += absl(s[i]);}printf("%lld\n",ans);}}else if(m==n){if(dep[au]>dep[av]) swap(au,av);if((dep[au]^dep[av])&1){if(sum) {puts("-1");}else{vec.clear();int v = av;while(dep[v]>dep[au]){vec.push_back(-s[v]);v = fa[v];}sort(vec.begin(),vec.end());int x = vec[vec.size()>>1];a[au] -= x; a[av] += x;for(int i=1; i<=n; i++) vis[i] = 0;dfs2(1,0);ans = absl(x);for(int i=1; i<=n; i++){ans += absl(s[i]);}printf("%lld\n",ans);}}else{if(absl(sum)&1) {puts("-1");}else{if(sum>0){for(int i=1; i<=n; i++) s[i] = -s[i],a[i] = -a[i];sum = -sum;}int x = (-sum)>>1;a[au] += x; a[av] += x;for(int i=1; i<=n; i++) vis[i] = 0;dfs2(1,0);ans = x;for(int i=1; i<=n; i++){ans += absl(s[i]);}printf("%lld\n",ans);}}}for(int i=1; i<=n; i++) fe[i] = vis[i] = fa[i] = 0;for(int i=1; i<=en; i++) e[i].v = e[i].nxt = 0;en = 0;return 0; }

總結(jié)

以上是生活随笔為你收集整理的AtCoder AGC004F Namori (图论)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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