F.The Best Path--ACM-ICPC 2016 Qingdao Preliminary Contest

https://nanti.jisuanke.com/t/29370

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3 2
3
4
5
1 2
2 3
4 3
1
2
3
4
1 2
2 3
2 4

样例输出

1
2
2
Impossible

题目来源
ACM-ICPC 2016 Qingdao Preliminary Contest


题解:

给一个图,每个点有一个权值,找欧拉通路或者欧拉回路,然后求路径上每个点异或结果的最大值;

首先判断有没有欧拉回路或者通路,用一下定理就好了,有且仅有两个度数为奇数的点则有欧拉通路,没有度数为奇数的点则有欧拉回路;

然后把对异或值有贡献的算上,有贡献的点就是d为奇数的点和(d/2)为奇数的点,因为经过偶数次的点相当于没有贡献;

代码:

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cmath>
#include <list>
#include <vector>
using namespace std;

const int N=100005;
int n,m,a[N],d[N];
int main(){
int t,u,v;
scanf("%d",&t);
while(t--){
int ans=0;
memset(d,0,sizeof(d));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
d[u]++;d[v]++;
}
int num=0;
for(int i=1;i<=n;i++){
if(d[i]&1)num++;
}
if(num==0){
for(int i=1;i<=n;i++){
if((d[i]/2)&1||d[i]&1)ans^=a[i];
}
int tmp=ans;
for(int i=1;i<=n;i++){
ans=max(ans,tmp^a[i]);
}
printf("%d\n",ans);
}
else if(num==2){
for(int i=1;i<=n;i++){
if((d[i]/2)&1||d[i]&1)ans^=a[i];
}
printf("%d\n",ans);
}
else printf("Impossible\n");
}
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信