AT2046 Namori 图论

正解:

解题报告:

传送门!

首先看数据范围可以发现要么是棵树要么是个奇环要么是个偶环

然后就分类讨论分别看下这几个情况

首先是棵树的

然后考虑有环的情况,这儿要分奇环偶环分开讨论下

然后就做完啦啦啦!

放下代码QAQ

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define ll long long

#define rg register

#define gc getchar()

#define t(i) edge[i].to

#define rp(i,x,y) for(rg int i=x;i<=y;++i)

#define my(i,x,y) for(rg int i=x;i>=y;--i)

#define e(i,x) for(rg int i=head[x];i;i=edge[i].nxt)

const int N=1e5+;

int n,m,head[N],ed_cnt,sz[N],st,to,sum,as,top,stck[N],g[N];

struct ed{int to,nxt;}edge[N<<];

bool jud;

bool vis[N];

il int read()

{

    rg char ch=gc;rg int x=;rg bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(int x,int y){edge[++ed_cnt]=(ed){x,head[y]};head[y]=ed_cnt;}

void dfs1(int x,int fa){e(i,x)if(t(i)^fa)if(sz[t(i)]){if(sz[t(i)]==sz[x])jud=;st=x;to=t(i);}else sz[t(i)]=-sz[x],dfs1(t(i),x);}

void dfs2(int x,int fa){vis[x]=;e(i,x)if(t(i)^fa && !((x==st && t(i)==to) || (x==to && t(i)==st)))dfs2(t(i),x),sz[x]+=sz[t(i)],g[x]+=g[t(i)];return;}

int main()

{

    n=read();m=read();rp(i,,m){int x=read(),y=read();ad(x,y);ad(y,x);}sz[]=;dfs1(,);

    rp(i,,n)sum+=sz[i];if(!jud)if(sum)return printf("-1\n"),;

    if(m==n)if(jud){if(sum&)return printf("-1\n"),;as+=abs(sum>>);sz[st]-=(sum>>);sz[to]-=(sum>>);}else g[st]=,g[to]=-;

    dfs2(,);

    rp(i,,n){if(g[i])stck[++top]=g[i]*sz[i];else as+=abs(sz[i]);}

    stck[++top]=;sort(stck+,stck+top+);int mid=stck[(top+)>>];

    rp(i,,top)as+=abs(stck[i]-mid);

    printf("%lld\n",as);

    return ;

}