【2018115模拟赛】T5传送机

5、传送机(sent.*)

问题描述:

黄黄同学要到清华大学上学去了。黄黄同学很喜欢清华大学的校园，每次去上课时总喜欢把校园里面的每条路都走一遍，当然，黄黄同学想每条路也只走一遍。
我们一般人很可能对一些地图是办不到每条路走一遍且仅走一遍的，但是黄黄同学有个传送机，他可以任意地将一个人从一个路口传送到任意一个路口。
可是，每传送一次是需要耗费巨大的内力的，黄黄同学希望可以用最少的传送次数完成游遍校园，你帮助他吗？因为黄黄同学只是游历校园，于是我们可以认为黄黄同学可以从任意点开始，到任意点结束。
注意：不必经过所有的点。输入格式：输入第一行一个整数N，表示黄黄的校园里一共有多少路口。第二行一个整数M，表示路口之间有M条路。后面M行，每行两个整数a、b，表示a与b之间有一条路，且路是双向的。输出格式：输出一行一个整数S，表示黄黄同学最少的传送次数。

输入样例：

3
2
1 2
2 3

输出样例：

0

数据规模：

对于100%的数据满足：N<=100000，M<=500000，1<=a，b<=N。

一句话概括，就是添加最少的边，是他构成一个欧拉回路，也就是广为人知的一笔画问题。

要满足一笔画，我们要先使它构成一个连通图且奇点个数不超过2（当然，那些只有一个点的连通块不用算，因为既然它们没有相连的边，删去也无所谓，用不着经过它们）

所以要加上max(连通快个数 - 1, 0)(由于可能所有连通块都只有一个节点，一条边也没有)

也就是把所有的连通块连起来，这样构成了一个连通图，然后还要考虑奇点的问题。

我们先考虑将连通块全部连起来对奇点的影响。我们可以这样考虑，对于没有奇点的连通块，直接将新增的两条边(连向其他块)都连到一个点，这样不会增加奇点个数。对于有2个及以上奇点的连通块，将新增的边连到任意两个奇点上，这样就减少了两个奇点。

对于两边的块，我们可以将有奇点的尽量放最边上，如果没有奇点的块，增加两个奇点是也就只有2个奇点，不会有影响；而对于有奇点的块，我们也可以认为没有影响，具体解释比较麻烦，大家可以自行画图论证。

最后再把奇点消到只有2个即可（一条边能消掉两个奇点）

最后得出算法。对于每个连通快 ans += (奇点个数 - 2) / 2 + 1

最后ans-=1（不解释）

这里我用并查集实现，大家看代码吧.

#include
using namespace std;
#define MAXN 100005
int N, M;
int fa[MAXN];
int s[MAXN], a[MAXN];
int find( int x ){
if ( x == fa[x] ) return x;
return fa[x] = find( fa[x] );
}
void Merge( int x, int y ){
x = find(x); y = find(y);
if ( x != y ) fa[x] = y;
}
int main(){
scanf( "%d%d", &N, &M );
if ( M == 0 ){ printf( "0\n" ); return 0; }
for ( int i = 1; i <= N; ++i ) fa[i] = i;
for ( int i = 1; i <= M; ++i ){
int x, y; scanf( "%d%d", &x, &y );
s[x]++; s[y]++;
Merge( x, y );
}
for ( int i = 1; i <= N; ++i ) a[find(i)] += s[i] % 2;
int ans(0);
for ( int i = 1; i <= N; ++i )
if ( s[i] > 0 && find(i) == i ) ans = ans + 1 + max( 0, ( a[i] - 2 ) / 2 );
printf( "%d\n", ans - 1 );
return 0;
}

完结撒花 刚好下课