The Best Path
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 18 Accepted Submission(s): 8
Problem Description
Alice is planning her travel route in a beautiful valley. In this valley, there are N lakes, and M
rivers linking these lakes. Alice wants to start her trip from one
lake, and enjoys the landscape by boat. That means she need to set up a
path which go through every river exactly once. In addition, Alice has a
specific number (a1,a2,...,an) for each lake. If the path she finds is P0→P1→...→Pt, the lucky number of this trip would be aP0XORaP1XOR...XORaPt. She want to make this number as large as possible. Can you help her?
rivers linking these lakes. Alice wants to start her trip from one
lake, and enjoys the landscape by boat. That means she need to set up a
path which go through every river exactly once. In addition, Alice has a
specific number (a1,a2,...,an) for each lake. If the path she finds is P0→P1→...→Pt, the lucky number of this trip would be aP0XORaP1XOR...XORaPt. She want to make this number as large as possible. Can you help her?
Input
The first line of input contains an integer t, the number of test cases. t test cases follow.
For each test case, in the first line there are two positive integers N (N≤100000) and M (M≤500000), as described above. The i-th line of the next N lines contains an integer ai(∀i,0≤ai≤10000) representing the number of the i-th lake.
The i-th line of the next M lines contains two integers ui and vi representing the i-th river between the ui-th lake and vi-th lake. It is possible that ui=vi.
Output
For each test cases, output the largest lucky number. If it dose not have any path, output "Impossible".
Sample Input
2
3 2
3
4
5
1 2
2 3
4 3
1
2
3
4
1 2
2 3
2 4
3 2
3
4
5
1 2
2 3
4 3
1
2
3
4
1 2
2 3
2 4
Sample Output
2
Impossible
Impossible
Source
题意:有 n个湖泊m条河流,现在 Alice 要从某点出发走遍所有河流一次且仅一次，问Alice走过的点的异或最大值是多少?
题解:这题每条边要走且仅走一次,那么这明显就是个欧拉(回)路,先判断一下连通分量的个数,如果有多个就是 "Impossible"，然后判断度为奇数的点的个数 ,如果不是0个或者2个,输出"Impossbie" ,如果度为奇数个数为 0 个,那么就是欧拉回路,那么就从度不为0且degree/2为奇数的每个点做异或,得到一个结果,得到的结果然后分别与每个点做异或,选择最大的.如果度为奇数的点是 2 个,那么每个点走的次数便是确定的,如果是度是偶数,那么degree/2为奇数的点参与异或,如果度为奇数,那么当(degree+1)/2为奇数时，此点参与异或。
附欧拉路的定义:
判定该图是否为Euler图，包括有向欧拉通路，有向欧拉回路，无向欧拉通路，无向欧拉回路：
有向欧拉通路：起点：出度-入度=1，终点：入度-出度=1，其它点：入度==出度
有向欧拉回路：所有点：入度==出度
无向欧拉通路：仅有两个奇度点
无向欧拉回路：无奇度点
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = ;
int a[N];
int father[N];
int degree[N];
int _find(int x)
{
if(x!=father[x]) father[x] = _find(father[x]);
return father[x];
}
void Union(int a,int b)
{
int x = _find(a);
int y = _find(b);
if(x==y) return ;
father[x] = y;
}
void init(int n)
{
for(int i=; i<=n; i++)
{
father[i] = i;
degree[i] = ;
}
}
int main()
{
int tcase,n,m;
scanf("%d",&tcase);
while(tcase--)
{
scanf("%d%d",&n,&m);
init(n);
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
for(int i=; i<=m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
degree[u]++;
degree[v]++;
Union(u,v);
}
int ans = ;
for(int i=; i<=n; i++)
{
if(degree[i]>)
{
if(_find(i)==i) ans++;
}
}
///连通分量个数
if(ans>)
{
printf("Impossible\n");
continue;
}
ans = ;
for(int i=; i<=n; i++)
{
if(degree[i]%!=) ans++;
}
///判断是否为欧拉路
if(ans!=&&ans!=)
{
printf("Impossible\n");
continue;
}
LL res = ;
if(ans==)
{
for(int i=; i<=n; i++)
{
int K = degree[i]/;
if(degree[i]!=&&K%==){
res = res^a[i];
}
}
LL MAX = -;
for(int i=; i<=n; i++)
{
int K = degree[i]/;
if(degree[i]!=){
MAX = max(MAX,res^a[i]);
}
}
res = MAX;
}
else
{
for(int i=; i<=n; i++)
{
int K = degree[i]/;
if(degree[i]%==&&K%==)
{
res = res^a[i];
}
if(degree[i]%==)
{
K = (degree[i]+)/;
if(K%==)
res = res^a[i];
}
}
}
printf("%lld\n",res);
}
return ;
}