CCF201512-4 送货

Posted on | In |

问题描述
　　为了增加公司收入，F公司新开设了物流业务。由于F公司在业界的良好口碑，物流业务一开通即受到了消费者的欢迎，物流业务马上遍及了城市的每条街道。然而，F公司现在只安排了小明一个人负责所有街道的服务。
　　任务虽然繁重，但是小明有足够的信心，他拿到了城市的地图，准备研究最好的方案。城市中有n个交叉路口，m条街道连接在这些交叉路口之间，每条街道的首尾都正好连接着一个交叉路口。除开街道的首尾端点，街道不会在其他位置与其他街道相交。每个交叉路口都至少连接着一条街道，有的交叉路口可能只连接着一条或两条街道。
　　小明希望设计一个方案，从编号为1的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。
输入格式
　　输入的第一行包含两个整数n, m，表示交叉路口的数量和街道的数量，交叉路口从1到n标号。
　　接下来m行，每行两个整数a, b，表示和标号为a的交叉路口和标号为b的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。

输出格式
　　如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p1, p2, p3, …, pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2最小，依此类推。
　　如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。
样例输入
4 5

1 2

1 3

1 4

2 4

3 4
样例输出
1 2 4 1 3 4
样例说明
　　城市的地图和小明的路径如下图所示。

样例输入
4 6
1 2
1 3
1 4
2 4
3 4
2 3
样例输出
-1
样例说明
　　城市的地图如下图所示，不存在满足条件的路径。

评测用例规模与约定
　　前30%的评测用例满足：1 ≤ n ≤ 10, n-1 ≤ m ≤ 20。
　　前50%的评测用例满足：1 ≤ n ≤ 100, n-1 ≤ m ≤ 10000。
　　所有评测用例满足：1 ≤ n ≤ 10000，n-1 ≤ m ≤ 100000。

思路

欧拉通路的判断

用栈来保存路径

只有80分

这个问题是一笔画问题，或者说是欧拉路径问题。所有需要判定图是否是连通图，然后再判定是否存在欧拉路径。判定是否是连通图，可以使用并查集来实现。判定是否存在欧拉路径的条件是：无向图的所有结点的出入度均为偶数，或者有2个出入度为奇数的结点。满足这个条件的图，必然能够找到欧拉路径。由于是从结点1出发，如果有2个出入度为奇数的结点，1的出入度必须为奇数。

程序说明：程序中，使用邻接表表示图，而且使用的是集合set。集合类set有自然排序的特征，构建好集合后不用专门排序。这样做,在用DFS寻找欧拉路径时，找到的第1个解即为字典顺序最小解。
并查集类需要是压缩的算法，不然时间上会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<set>
#include<vector>
#include <iostream>
#include<cstring>
#include<stack>//!!
using namespace std;
bool vis[10000][10000];//bool!!
//想到用二维存储 顶点a 到顶点b的边访问过!! 
int n,m;
stack<int> path;
//!!vector<set<int> >g=vector<set<int> >(10000);

set<int> g[10000];//领接表存储图 
class unionset{
public:
    vector<int> parent;
	
    unionset(int n){
    parent=vector<int>(n+1,0);
        for(int i=1;i<=n;i++)
	parent[i]=i;
	}
	
	bool Union(int u1,int u2){
		int p1=find(u1);
		int p2=find(u2);
		if(p1==p2) return false;
        parent[p1]=p2;
        return true;
		
	}
    int find(int num){
        if(num!=parent[num]){
            parent[num]=find(parent[num]);//find(num)一直自己调用自己 错的 find(parent[num]) 往上回溯
        }
        return parent[num];
    }
	
};
void dfs(int cur){
	//cout<<cur<<" "; 

	 for(set<int>::iterator it=g[cur].begin(); it!=g[cur].end(); it++) {
	 	if(vis[cur][*it]) continue;
		vis[cur][*it]=true;
		vis[*it][cur]=true;
		dfs(*it);
	 }
		path.push(cur);
} 
int main(){
	cin>>n>>m;
	int a,b;
	unionset u(n);
	
	for(int i=0;i<m;i++){
		cin>>a>>b;
		g[a].insert(b);
		g[b].insert(a);
		u.Union(a,b);
	}
	
	int t1=u.find(1); 

	for(int i=2;i<=n;i++)
	{
		if(u.find(i)!=t1) {
		cout<<-1<<endl;
		return 0;	
		}
	}  
	 int count = 0;
        for(int i=1; i<=n; i++)
            if(g[i].size() % 2 == 1)
                count++;
        if(!(count == 0 || (count == 2 && g[1].size() % 2 == 1)))
        {
        			cout<<-1<<endl;
		return 0;	
		}

	memset(vis,0,sizeof(vis));
		dfs(1);
	int t;
        while(!path.empty()) {
            t = path.top();
            path.pop();
 
            cout << t << ' ';
        }
        cout << endl;


}

参考博客

http://www.voidcn.com/article/p-skxnamth-bqh.html