本文共 1989 字,大约阅读时间需要 6 分钟。
614. 游历校园
★★ 输入文件:sent.in
输出文件: sent.out
简单对比 时间限制:1 s 内存限制:128 MB 【问题描述】
刷完牙洗完脸,黄黄同学就要上课去了。可是黄黄同学每次去上课时总喜欢把校园里面的每条路都走一遍,当然,黄黄同学想每条路也只走一遍。我们一般人很可能对一些地图是办不到每条路走一遍且仅走一遍的,但是黄黄同学有个传送机,他可以任意地将一个、人从一个路口传送到任意一个路口。
可是,每传送一次是需要耗费巨大的内力的,黄黄同学希望可以用最少的传送次数完成游遍校园,你能帮助他吗 ?
因为黄黄同学只是游历校园,于是我们可以认为黄黄同学可以从任意点开始,到任意点结束。
【输入文件】
输入文件 sent.in 的第一行有一个整数 N ,表示黄黄的校园里一共有多少路口。
第二行有一个整数 M ,表示路口之间有 M 条路。
后面 M 行每行两个整数 a 、 b 表示 a 与 b 之间有一条路,且路是双向的。
【输出文件】
输出文件 sent.out 只包括一个整数 s ,表示黄黄同学最少的传送次数。
【样例输入】
3
2
1 2
2 3
【样例输出】
0
【数据范围】
对于 100 %的数据,保证 N ≤ 100000 , K ≤ 500000 , 1 ≤ a , b ≤ N 。
一开始不会做 后来听PB大神讲了一下
就是求类似欧拉路的思想
判断一个联通块内有多少点有奇数条边
如果点数大于2 则需要传送 (点-2)/2次
不同联通块间还需传送一次
但是如果那一个联通块只有一个点 则不需要
因为他要走完所有边 而不是所有点
可以用bfs判断连通性 也可以并查集
我写的bfs判断的
#include#include #include using namespace std;const int lim=100011;const int len=500055;struct self{int x,y;}s[len*2];int first[len*2],nxt[len*2];int num[lim];int m,n;int tempn;bool flag[lim]={0};int z=0,a,ans;int head,tail;int q[lim];void bfs(int i){ head=tail=1; q[1]=i; int tot=0; if(num[i]%2==1)tot++; while(head<=tail) { for(int e=first[q[head]];e!=-1;e=nxt[e]) { if(!flag[s[e].y]) { flag[s[e].y]=1; tail++; q[tail]=s[e].y; if(num[s[e].y]%2==1)tot++; } } head++; } if(tot>2)z=z+(tot-2)/2;} int main(){ freopen("sent.in","r",stdin);freopen("sent.out","w",stdout); memset(first,-1,sizeof(first)); memset(nxt,-1,sizeof(nxt)); scanf("%d%d",&m,&n); for(a=1;a<=n;a++) { scanf("%d%d",&s[a].x,&s[a].y); if(s[a].x==s[a].y)continue; s[a+n].x=s[a].y;s[a+n].y=s[a].x; nxt[a]=first[s[a].x];first[s[a].x]=a; nxt[a+n]=first[s[a].y];first[s[a].y]=a+n; num[s[a].x]++;num[s[a].y]++; } for(a=1;a<=m;a++) if(!flag[a]&&num[a]>=1) { flag[a]=1; bfs(a); z++; } z--; cout< <<'\n'; return 0;}
转载地址:https://blog.csdn.net/li412302070/article/details/12776581 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!