概述
前言
这题好牛逼啊。
题目大意
给你一颗全白的树或环套树。
你每次可以选择一条连接两个同色点的边,将两个端点反色。
问变成全黑的最小步数,要求判断无解。
树的做法
树是一个二分图,看起来很棒的样子。
我们不妨设深度为奇数(根的深度为1)的点是一个空位,而深度为偶数的点有一个硬币。
我们发现,一次操作相当于将一个硬币移到相邻的空位。
最终要求原本是空位的点都被硬币填满。
那么只有硬币数等于空位数才有解。
不妨记空位为1,硬币为-1。
si表示子树和,最小的答案是
∑ni=1abs(si)
因为这个是一定要从这个子树运出的硬币数或运进的硬币数,这个值代表其和父亲边的操作次数。这个式子显然是下界。
而不难发现该下界可以达到。对于一个点,我们把它的儿子分为运进儿子和运出儿子,每次把运出儿子的一个硬币匹配到运进儿子,当然可行。
这个做法很重要,接下来我们来解决环套树,分两种情况讨论。
奇环
任意断开环上一边u和v,变成树。
u和v一定属于二分图同一侧,我们操作一次u-v,显然是在u和v各增加一个硬币或各减少一个硬币。
不妨计算出变成树后所多余或所缺少的硬币数量,如果是奇数则无解,否则均摊到u和v上。
然后像树的做法做一遍即可。
偶环
同样任意断开一边u和v。
然后设u-v这条边操作了x次(可以是负数),那么u上增加x个硬币,v上则减少x个硬币。
设ki表示子树i最终带x的系数,显然只有0、1、-1。
那么答案是
abs(x)+∑ni=1abs(kix+si)
k为0的可以直接加进答案,剩下的可以看做数轴上若干点,选一个点使得这些点到该点距离和最小,是经典问题,取中位数最优。
#include<cstdio>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=100000+10;
int h[maxn],go[maxn*2],nxt[maxn*2],fa[maxn],co[maxn],kk[maxn],bb[maxn],sta[maxn];
bool bz[maxn];
int i,j,k,l,t,n,m,u,v,a,b,x,tot,top,num;
ll ans;
bool czy,gjx;
void add(int x,int y){
go[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
int getfa(int x){
if (!fa[x]) return x;
int t=getfa(fa[x]);
co[x]=co[x]^co[fa[x]];
return fa[x]=t;
}
void travel(int x,int y){
bz[x]=1;
int t=h[x];
while (t){
if (go[t]!=y){
if (bz[go[t]]){
u=x;v=go[t];
if (co[u]==co[v]) gjx=1;
}
else{
co[go[t]]=co[x]^1;
travel(go[t],x);
}
}
t=nxt[t];
}
}
void dfs(int x,int y){
int t=h[x];
while (t){
if (go[t]!=y&&!(x==u&&go[t]==v||x==v&&go[t]==u)){
dfs(go[t],x);
kk[x]+=kk[go[t]];
bb[x]+=bb[go[t]];
}
t=nxt[t];
}
}
int main(){
scanf("%d%d",&n,&m);
fo(i,1,m){
scanf("%d%d",&j,&k);
add(j,k);add(k,j);
/*a=getfa(j);b=getfa(k);
if (a!=b){
add(j,k);add(k,j);
fa[a]=b;
co[a]=co[j]^co[k]^1;
}
else{
u=j;v=k;
if (co[j]==co[k]) gjx=1;
}*/
}
//fo(i,1,n) getfa(i);
/*if (!co[1])
fo(i,1,n) co[i]^=1;*/
co[1]=1;
travel(1,0);
fo(i,1,n)
if (co[i]) bb[i]=1;else bb[i]=-1;
fo(i,1,n) num+=bb[i];
if (m==n-1){
if (num){
printf("-1n");
return 0;
}
}
else{
if (gjx){
if (num%2==1){
printf("-1n");
return 0;
}
bb[u]-=num/2;bb[v]-=num/2;
ans+=(ll)abs(num/2);
}
else{
if (num){
printf("-1n");
return 0;
}
kk[u]=1;kk[v]=-1;
}
}
dfs(1,0);
fo(i,1,n)
if (!kk[i]) ans+=(ll)abs(bb[i]);
else{
if (kk[i]) bb[i]=-bb[i];
sta[++top]=bb[i];
}
sta[++top]=0;
sort(sta+1,sta+top+1);
x=sta[(top+1)/2];
fo(i,1,top) ans+=(ll)abs(sta[i]-x);
printf("%lldn",ans);
}
最后
以上就是忧郁哑铃为你收集整理的[agc004f]Namori前言题目大意树的做法奇环偶环的全部内容,希望文章能够帮你解决[agc004f]Namori前言题目大意树的做法奇环偶环所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复