题目链接
https://atcoder.jp/contests/agc004/tasks/agc004_f
题解
神仙题..
首先考虑树的情况, 树是二分图, 因此假设我们对二分图进行黑白染色, 那么操作就变成了, 每次选择两个不同色的点来取反. 然后再把黑色视作标记, 那么问题就变成了, 初始一些点上有标记, 每次可以把标记沿着边移动到一个没标记的点, 要把标记全部移动到和原来不同的位置上, 求最小代价!
然后这个问题的做法就是, 首先如果两种颜色个数不同就无解, 否则考虑一个下界, 对于每一条边而言, 它至少要运送标记的次数等于其一端子树内黑白点个数差的绝对值. 对所有的边求和就是答案的下界, 而我们也能构造出来一种达到这个下界的方案, 构造详见官方题解.
然后考虑基环树. 当环是奇环和偶环时, 其作用不同, 因此需要分类讨论.
当环是偶环时, 非树边的作用是多了一条运送标记的边. 假设这条边运送了 \(x\)个标记 (可正可负), 那么其所影响的是环上的点, 需要最小化的是一个 \(\sum |x-a_i|\) 的形式, 直接取中位数即可.
当环是奇环时, 非树边的作用是可以给两个端点的标记同时 \(+1\)或 \(-1\). 显然 \(+1\)和 \(-1\)都出现是不优的, 由于操作可逆可以假设是 \(+1\) (否则交换初始状态和终止状态). 在这种情况下, 若两种颜色个数奇偶性不同就无解, 否则执行这种操作的次数 \(x\)是确定的 (因为初始和终止时两种颜色点数确定). 那么就可以认为给这两个端点分别加了 \(x\) 个标记, 然后再执行树的算法即可.
时间复杂度 \(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;
- }
来源: http://www.bubuko.com/infodetail-3234220.html