BZOJ2503: 相框【欧拉回路】

2503: 相框

【题目描述】

传送门

【题解】

题解原引某位大佬。

题目大意:给定一张无向图,每次可以进行以下两种操作:
1.将一个点分裂成一些点,原先这个点连接的每条边任选一个新点进行连接
2.将两个度数为1的点合并为1个点
求将这个图变成一个环的最小操作次数
首先我们考虑拆
由于终态每个点度数最多为2,因此我们将每个度数大于2的点都拆成一些度数为2的点,如果有零头,留下一个度数为1的点
由欧拉通路的相关结论可知,按照这种拆法,一个有k(k>=2)个奇度数点的连通块存在一种方案可以被拆成\frac{k}{2}条链,一个全是偶度数点的连通块可以被拆成一个环
然后如果得到的连通块不只有一个,拆掉所有的环。(当然如果一个环是由上一步拆分得到的,那么直接在上一步拆分中让其成为一条链即可)
最后把所有的链连起来得到一个环
注意数组别开小了

代码如下

#include<cstdio>
using namespace std;
const int MAXN=1005,MAXE=50005;
int n,m,Ans,cnt,D[MAXN+2*MAXE],fa[MAXN+2*MAXE];bool vis[MAXN+2*MAXE],flg[MAXN+2*MAXE];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
int DO(int y){if(y==0) fa[y=++n]=n;return y;}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),D[DO(x)]++,D[DO(y)]++,fa[get(x)]=get(y);
    for(int i=1;i<=n;i++){
        if(D[i]&1) cnt++,vis[get(i)]=1;
        if(D[i]>2) Ans++,flg[get(i)]=1;
    }
    int Num=0;
    for(int i=1;i<=n;i++)
    if(get(i)==i&&D[i]) Num++;
    for(int i=1;i<=n&&Num>1;i++)
    if(i==get(i)&&D[i]&&!vis[i]){cnt+=2;if(!flg[i]) Ans++;}
    printf("%d\n",Ans+(cnt>>1));
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部