【u224】传送机
Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
刷完牙洗完脸，黄黄同学就要上课去了。可是黄黄同学每次去上课时总喜欢把校园里面的每条路都走一遍，当然，黄黄同学想每条路也只走一遍。我们一般人很可能对一些地图是办不到每条路走一遍且仅走一遍的，但是黄黄同学有个传送机，他可以任意地将一个、人从一个路口传送到任意一个路口。 可是，每传送一次是需要耗费巨大的内力的，黄黄同学希望可以用最少的传送次数完成游遍校园，你能帮助他吗? 因为黄黄同学只是游历校园，于是我们可以认为黄黄同学可以从任意点开始，到任意点结束。
【输入格式】
输入文件sent.in的第一行有一个整数N，表示黄黄的校园里一共有多少路口。 第二行有一个整数M，表示路口之间有M条路。 后面M行每行两个整数a、b表示a与b之间有一条路，且路是双向的。
【输出格式】
输出文件sent.out只包括一个整数s，表示黄黄同学最少的传送次数。
【数据规模】
对于100％的数据，保证N≤100000，K≤500000，1≤a，b≤N。
Sample Input1
3
2
1 2
2 3
Sample Output1
0
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u224
【题解】
对于一个联通图来说;
只有当它的奇点(度数为奇数的点)的个数为2或0的时候,才能完成一笔画;
如果奇点的个数>2,则需要x/2笔画;
(本题中需要传送机为(x-2)/2)
x为奇点的个数;
(在一个连通图中,奇点的个数总是偶数的);
如果一张图里面有不同的连通块;
那么不同的连通块之间还要一个传送器;
(连通块用dfs求感觉比并查集方便)
题目说的是走遍所有的路;
所以如果一个连通块中只有一个点,那么就不必加上传送机;
【完整代码】
#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <vector>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int MAXN = 1e5+100;int n,m,tj,ji[MAXN],siz[MAXN],cnt,num=0;vector <int> g[MAXN];bool bo[MAXN];void dfs(int x){ cnt++; bo[x] = true; int len = g[x].size(); if (len&1)tj++; rep1(i,0,len-1) { int y = g[x][i]; if (!bo[y]) dfs(y); }}int main(){ //freopen("F:\\rush.txt","r",stdin); rei(n);rei(m); rep1(i,1,m) { int x,y; rei(x);rei(y); g[x].pb(y); g[y].pb(x); } rep1(i,1,n) if (!bo[i]) { tj = 0;cnt = 0; dfs(i); siz[++num] = cnt; ji[num] = tj; } memset(bo,false,sizeof bo); int ans = 0,tt = 0; rep1(i,1,num) { if (ji[i]>2) ans+=(ji[i]-2)/2; if (siz[i]>1) tt++; } ans+=tt-1; printf("%d\n",ans); return 0;}