淘宝客网站 备案,十大广告设计公司简介,滨州北京网站建设,上海网站建设工资多少Description P大的基础电路实验课是一个无聊至极的课。每次实验#xff0c;T君总是提前完成#xff0c;管理员却不让T君离开#xff0c;T君只能干坐在那儿无所事事。先说说这个实验课#xff0c;无非就是把几根导线和某些元器件#xff08;电阻、电容、电感等#xff09;…Description P大的基础电路实验课是一个无聊至极的课。每次实验T君总是提前完成管理员却不让T君离开T君只能干坐在那儿无所事事。 先说说这个实验课无非就是把几根导线和某些元器件电阻、电容、电感等用焊锡焊接起来。 为了打发时间T君每次实验做完后都在焊接一些诡异的东西这就是他的杰作 T君不满足于焊接奇形怪状的作品强烈的破坏欲驱使他拆掉这个作品然后将之焊接成规整的形状。这会儿T君正要把这个怪物改造成一个环形当作自己的相框步骤如下 T君约定了两种操作 1. 烧熔一个焊点使得连接在焊点上的某些导线相分离或保持相连可以理解为把焊点上的导线划分为若干个类相同类中的导线相连不同类之间的导线相离 2. 将两根导线的自由端即未与任何导线相连的一端焊接起来。 例如上面的步骤中先将A点烧熔使得导线1与导线2、4点分离再将D点烧熔使得4、5与3、7相离再烧熔E使7与6、8相离最后将1、7相连。 T君想用最少的操作来将原有的作品改造成为相框(要用上所有的导线)。 Input 输入文件的第一行共有两个整数n和m — 分别表示原有的作品的焊点和导线的数量 (0 ≤ n ≤ 1 000, 2 ≤ m ≤ 50 000)。焊点的标号为1~n。 接下来的m行每行共有两个整数 — 导线两端所连接的两个焊点的标号若不与任何焊点相连则将这一端标号为0。 原有的作品可能不是连通的。 某些焊点可能只有一根导线与之相连在该导线的这一端与其他导线相连之前这些焊点不允许被烧熔。 某些焊点甚至没有任何导线与之相连由于T君只关心导线因此这些焊点可以不被考虑。 Output 输出文件只包含一个整数——表示T君需要将原有的作品改造成相框的最少步数。 Sample Input 6 8 1 2 1 3 3 4 1 4 4 6 5 6 4 5 1 5 Sample Output 4 HINT 30%的数据中n≤10; 100%的数据中n≤1000。 这个还是挺考思路的还要求一些图论性质 首先我们要把每个联通块拆开又因为要构成一个简单环所以要拆成链状 像这样 那么对于每一个欧拉回路我们熔掉一个点就可以搞成上面n多个这东西 对于一个奇度点我们拆一次也可以搞成这样题目说了随便选边 然后就可以合并了 代码如下 //MT_LI
#includecmath
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
using namespace std;
int fa[110000];
int findfa(int x)
{if(fa[x]!x)fa[x]findfa(fa[x]);return fa[x];
}
int n,m;
int v[110000],er[110000];//是不是欧拉图有没有被拆过
int degree[110000];
int main()
{scanf(%d%d,n,m);for(int i1;in;i)fa[i]i;for(int i1;im;i){int x,y;scanf(%d%d,x,y);if(!x)xn,fa[x]x;if(!y)yn,fa[y]y;degree[x];degree[y];int fxfindfa(x),fyfindfa(y);if(fxfy)continue;fa[fy]fx;}int ans0,sum0;for(int i1;in;i){if(!degree[i])continue;if(degree[i]1){sum;er[findfa(i)]1;} if(degree[i]2){ans;v[findfa(i)]1;}}int cnt0;for(int i1;in;i)if(fa[i]idegree[i])cnt;for(int i1;in;i)if(cnt1degree[i]fa[i]i!er[i]){sum2;if(!v[i])ans;}printf(%d\n,anssum/2);return 0;
} 转载于:https://www.cnblogs.com/MT-LI/p/9844281.html
