The Best Path https://nanti.jisuanke.com/t/29370
看完直觉是欧拉回路
最后考虑进行异或得出最大值, 考虑异或偶数次相当于没改变一切, 只考虑异或奇数次的点, 那么次数如何算呢?(度数 + 1)/2, 不就是经过这个点的次数么, 最后欧拉路径得多考虑一下, 因为欧拉路径起点不唯一 , 所以进行枚举下, 最后得出最大值
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int maxn = 1e5 + 10;
- int n, m;
- int a[maxn];
- int degree[maxn];
- int main()
- {
- freopen("in.txt","r",stdin);
- int t;
- scanf("%d", &t);
- while (t--) {
- memset(degree, 0, sizeof(degree));
- scanf("%d%d", &n, &m);
- for (int i = 1; i <= n; i++)
- {
- scanf("%d", &a[i]);
- }
- int u, v;
- for (int i = 1; i <= m; i++)
- {
- scanf("%d%d", &u, &v);
- degree[u]++;
- degree[v]++;
- }
- int cnt = 0;
- for (int i = 1; i <= n; i++)
- {
- if (degree[i] & 1) {
- cnt++;
- }
- }
- if (cnt != 0 && cnt != 2) {
- printf("Impossible\n");
- continue;
- }
- int ans = 0;
- for (int i = 1; i <= n; i++)
- {
- degree[i] = (degree[i] + 1)>> 1;// 计算每个点经过的次数, 每个点肯定都要经过而且经过的次数不一定.
- if (degree[i] & 1) // 如果点经过的次数为偶数次那么异或完以后还是 0, 只有奇数次的点异或才有意义
- {
- ans ^= a[i];
- }
- }
- int tmp = ans;
- if (cnt == 0)// 如果是欧拉回路, 起点要多经过一次, 所以要枚举一边所有的点作为起点找到最大值
- {
- for (int i = 1; i <= n; i++)
- {
- ans = max(ans, tmp ^ a[i]);
- }
- }
- printf("%d\n", ans);
- }
- return 0;
- }
- F-The Best Path
来源: http://www.bubuko.com/infodetail-2732279.html