Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 430 Accepted Submission(s): 181
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?
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 integersN (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.
Thei -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 .
For each test case, in the first line there are two positive integers
The
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
Sample Output
2 Impossible
Source
【题解】
毒题。也不说有没有重边啊什么的。不连通怎么办？？
最后是:
如果这个图没有联通。则输出impossible。如果度数为奇数的点的个数不为0或2则Impossible.
如果奇数度数的点的个数为2；
则两个奇数度数的点为这条路径的起点和终点。
然后只要用ans =0;
异或起点和终点。
中间还可能有其他点！！
一个点的度数/2 就是进出这个点的次数。
如果为偶数则根据异或的结合律为0；不用异或。
否则为奇数就异或。
that‘s it
然后是奇数度数的点的个数为0；
则把所有点的度数/2 为奇数的点和初始ans异或下。
最后还要回到起点一次。所以每个点都当做起点试试能不能更优。
具体的看代码吧。反正这题太毒了。
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_SIZE = 109000;
int t, n, m, a[MAX_SIZE], f[MAX_SIZE], du[MAX_SIZE], ans;
bool no_ans;
int get_father(int x)
{
if (f[x] == x)
return x;
else
f[x] = get_father(f[x]);
return f[x];
}
void input_data()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int num = n;
for (int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
du[x]++; du[y]++;
int r1 = get_father(x);//用并查集获取图的连通性
int r2 = get_father(y);
if (r1 != r2)
{
num--;
f[r1] = r2;
}
}
if (num != 1)
no_ans = true;
}
void init()
{
for (int i = 1; i <= MAX_SIZE - 1; i++)
f[i] = i;
for (int i = 1; i <= MAX_SIZE - 1; i++)
du[i] = 0;
no_ans = false;
ans = 0;
}
void get_ans()
{
int num = 0;
for (int i = 1; i <= n; i++)
if ((du[i] % 2) == 1)
num++;
if (num == 0) //欧拉回路
{
for (int i = 1; i <= n; i++)
if ((du[i] / 2) % 2 == 1)//进出某个点的次数为奇数则多异或一下
ans ^= a[i];
int max_ans = ans;
max_ans ^= a[1];
for (int i = 2; i <= n; i++)//枚举哪个点是起点。求最大值
max_ans = max(max_ans, ans ^ a[i]);
ans = max_ans;
}
else
if (num == 2)//欧拉通路
{
for (int i = 1; i <= n; i++)
if ((du[i] % 2) == 1)//起点和终点
ans ^= a[i];
else
if (((du[i] / 2) % 2) == 1)//中间的需要异或的点。
ans ^= a[i];
}
else
{
no_ans = true;
return;
}
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
scanf("%d", &t);
while (t--)
{
init();
input_data();
if (no_ans)
{
printf("Impossible
");
continue;
}
get_ans();
if (no_ans)
{
printf("Impossible
");
continue;
}
printf("%d
", ans);
}
return 0;
}