首页 > 代码库 > hdu5883:The Best Path 欧拉图的性质和应用
hdu5883:The Best Path 欧拉图的性质和应用
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5883
题目大意: 给定 n 个点, m 条边的图，每个点有权值，求所给图是否是欧拉图， 如果是， 求出所经过点的权值做异或运算的最大值。
吐槽：这题给的数据竟然不用判断是否联通，坑了我几发MLE，不过也骗过啦
题目思路：首先异或运算满足交换律，所以与点的遍历顺序无关。
其次，对于欧拉图的判定，奇数度的结点个数为０是欧拉回路，为２是欧拉通路。
然后，没经过一个点，该点的度数减去２，所以可以判断出一个点是否异或的公式为：对于任意点 i ,degree[i] / 2 % 2 = ans, ans为１表示该点需要异或运算（偶数个相同的数做异或运算抵消）。这是突然发现样例一过不去了，说明我们需要对欧拉图的起点和终点做特殊处理。
- 欧拉通路：两个奇数度结点在开始和结束的时候必然单独经过一次点，所以对这两个点单独做一次异或运算，然后各自的度减去１；
- 欧拉回路：对于回路只需要枚举起点，因为在起点出发和最终到达都只能单独算一次经过该点，所以起点要求多算一次。因为要求最大结果，O(n)枚举所有结果求最大即可
代码实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 100000 + 1; 5 int n, m, a[N], du[N], vis[N]; 6 vector<int> mp[N]; 7 8 void init() { 9 for (int i = 0; i < N; ++ i) mp[i].clear();10 memset(du, 0, sizeof(du));11 memset(vis, 0, sizeof(vis));12 }13 14 void dfs(int p) {15 vis[p] = 1;16 for (int i = 0; i < mp[p].size(); ++ i) {17 if(!vis[mp[p][i]]) dfs(mp[p][i]); 18 }19 }20 21 void addedge(int u, int v) {22 mp[u].push_back(v);23 mp[v].push_back(u);24 ++du[u]; ++du[v];25 }26 27 int main()28 {29 int t;30 scanf("%d", &t);31 while(t--){32 init();33 scanf("%d%d", &n, &m);34 for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);35 for (int i = 1; i <= m; ++ i) {36 int u, v;37 scanf("%d%d", &u, &v);38 addedge(u, v);39 }40 int ans = 0;41 for (int i = 1; i <= n; ++ i) {42 if(!vis[i]) {43 ans++;44 if(ans>1) break;45 dfs(i);46 }47 }48 if(ans > 1) {49 printf("Impossible\n");50 continue;51 }52 ans = 0;53 for (int i = 1; i <= n; ++ i) if(du[i]%2) ans++;54 int ret = 0;55 if(ans == 0) {56 for (int i = 1; i <= n; ++ i) if(du[i]/2%2) ret ^= a[i];57 ret ^= a[1];58 for (int i = 2; i <= n; ++ i) ret = max(ret, ret^a[i]);59 printf("%d\n", ret);60 } else if (ans == 2) {61 for (int i = 1; i <= n; ++ i) if(du[i]%2) ret^=a[i], du[i]--;62 for (int i = 1; i <= n; ++ i) if(du[i]/2%2) ret ^= a[i];63 printf("%d\n", ret);64 } else printf("Impossible\n");65 }66 return 0;67 }
hdu5883:The Best Path 欧拉图的性质和应用
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。