bzoj 2503 相框分类讨论

题目大意：给定一张无向图，每次可以进行以下两种操作：
1.将一个点分裂成一些点，原先这个点连接的每条边任选一个新点进行连接
2.将两个度数为1的点合并为1个点
求将这个图变成一个环的最小操作次数

我们简单画一画可以发现，整个的答案只与度有关。
如果最后形成了一个环。
那么环上的点的度一定为2
不在环上的点则都为不连边的点，度一定为0
我们一定要拆了所有度大于2的点。
首先忽略所有度为0的点。
现在考虑所有的边都在一个连通块内的情况。
对于一个度大于2的点。
如果他的度是奇数，那么一定拆成了一堆度为2的点与一个度为1的点。
如果他的度是偶数，那么一定拆成了一堆度为2的点。
拆完所有度大于2的点之后。
度为1的点一定有偶数个，只需要每一次合并两个即可。
然后我们考虑边不都在一个连通块的情况
即度不为0的点构成了几个连通块。
那么对于每一个连通块，我们一定是把这个连通块搞成有两个度为1的点，其余的块内点的度均为2。
所以这时候与上一种情况有区别的是，上一种情况可能存在操作或者不操作后块内所有的点的度都为2，这时候我们要标记是否拆分了点，因为如果拆分过点的话我们还可以拆分成两个度为1的点，和一堆度为2的点，这只用了一次操作，如果我们后拆的话会多一次操作，注意这里即可。
其余的正常做。

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstdio>

 #define N 200007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,ans,blo;

 int bel[N],flag[N],vis[N],du[N],odd[N];

 int cnt,hed[N],rea[N],nxt[N];

 void add(int u,int v)

 {

     nxt[++cnt]=hed[u];

     hed[u]=cnt;

     rea[cnt]=v;

 }

 void dfs(int u,int blo)

 {

     vis[u]=,bel[u]=blo;

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (vis[v])continue;

         dfs(v,blo);

     }

 }

 int main()

 {

     memset(hed,-,sizeof(hed));

     n=read(),m=read();

     for(int i=;i<=m;i++)

     {

         int x=read(),y=read();

         if(x==)x=++n;

         if(y==)y=++n;

         add(x,y),add(y,x);

         du[x]++,du[y]++;

     }

     for (int i=;i<=n;i++)

         if (!vis[i]&&du[i]!=)

         {

             blo++;

             dfs(i,blo);

         }

     for (int i=;i<=n;i++)

         if (du[i]==)

         {

             odd[bel[i]]++;

             if(odd[bel[i]]==) ans++,odd[bel[i]]=;

         }

     for (int i=;i<=n;i++)

     {

         if(!du[i])continue;

         if(du[i]>)

         {

             ans++;

             du[i]=(du[i]&?:);

             if(du[i]==)

             {

                 odd[bel[i]]++;

                 if(odd[bel[i]]==)ans++,odd[bel[i]]=;

             }

             else flag[bel[i]]=;

         }

     }

     if(blo!=)

     {

         for (int i=;i<=blo;i++)

             if (!odd[i]&&!flag[i])ans++;

         ans+=blo;

     }

     else if (odd[]!=)ans++;

     printf("%d\n",ans);

 }

巴特西

bzoj 2503 相框分类讨论

最新文章

热门文章

巴特西

bzoj 2503 相框 分类讨论

最新文章

热门文章

bzoj 2503 相框分类讨论