【bzoj3706】【FJ2014集训】反色刷

2014年9月24日1,4220

【题目描述】

给一张无向图,边有黑白两种颜色,现在你有一堆反色刷,可以从任意点开始刷,经过若干条边后回到起点。

现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。

因为某种原因,边的颜色是会改变的,于是。。

需要支持以下操作:

1 x 把第x条边反色(编号从0~m-1)

2   询问当前图中最少需要多少个反色刷

【输入格式】

第一行两个整数n m表示这张图有n个点m条边

接下来m行 每行3个整数 u v c表示一条无向边和这条边的颜色(0为白色 1为黑色)

接下来一个整数q 表示有q个操作

接下来q行为操作 描述如上

【输出格式】

对于每个询问 输出一行一个整数

表示最少需要的反色刷个数 如果没有合法方案输出-1

【样例输入】

6 6

1 2 1

2 3 1

1 3 1

4 5 1

5 6 1

4 6 1

14

2

1 0

2

1 1

1 2

2

1 3

1 4

1 5

2

1 3

1 4

1 5

2

【样例输出】

2

-1

1

0

1

【数据范围】

30%   n <= 20, m <= 29 ,q <= 64

60%   n <= 5000, m <= 5215 ,q <= 11308

100% n,m,q <= 1000000, c < 2,没有重边自环

来自出题人cxjyxxw_me的题解

首先猜想一个性质:如果有某个点连出的黑边度为奇数,则无解,否则必然有解。

证明:用欧拉回路去模拟,易证。

再猜想一个性质:如果有解的话,ans=图中含有黑边的联通块数。

证明:首先构造一个可行解,随便找一个有黑度的点,随便走向一个连出的黑边,一直走,直到回到这个点为止(显然一定会回到这个点)。现在考虑在同一个联通块的两个可行路径,设两个路径分别为u->blabla_u->u和v->blabla_v->v,他们的起点必然联通,设这段路径为u_v,则这两个路径可以合并为u->u_v->v->blabla_v->v->u_v->u->blabla_u->u。最后一个联通块的所有路径可以合并为一个,证毕。