...
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
A B C D E F G H I J Q&A
.
.
Arc of Dream
1 = 1
a
i
= AX ∗ a
i−1
+ AY ∗ 1
b
i
= BX ∗ b
i−1
+ BY ∗ 1
a
i
b
i
= (AX ∗ a
i−1
+ AY)(BX ∗ b
i−1
+ BY)
= AX ∗ BX ∗ a
i−1
b
i−1
+ AY ∗ BY ∗ 1
AX ∗ BY ∗ a
i−1
+ BX ∗ AY ∗ b
i−1
+
AoD(i) = AoD(i − 1) + a
i−1
b
i−1
1
a
n
b
n
a
n
b
n
AoD(n)
=
1 0 0 0 0
AY AX 0 0 0
BY 0 BX 0 0
AY · BY AX · BY AY · BX AX · BX 0
0 0 0 1 1
n
1
a
0
b
0
a
0
b
0
0
watashi blog.watashi.ws
2013 Multi-University Training Contest 9
...
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
A B C D E F G H I J Q&A
.
.
Arc of Dream
1 = 1
a
i
= AX ∗ a
i−1
+ AY ∗ 1
b
i
= BX ∗ b
i−1
+ BY ∗ 1
a
i
b
i
= (AX ∗ a
i−1
+ AY)(BX ∗ b
i−1
+ BY)
= AX ∗ BX ∗ a
i−1
b
i−1
+ AY ∗ BY ∗ 1
AX ∗ BY ∗ a
i−1
+ BX ∗ AY ∗ b
i−1
+
AoD(i) = AoD(i − 1) + a
i−1
b
i−1
1
a
n
b
n
a
n
b
n
AoD(n)
=
1 0 0 0 0
AY AX 0 0 0
BY 0 BX 0 0
AY · BY AX · BY AY · BX AX · BX 0
0 0 0 1 1
n
1
a
0
b
0
a
0
b
0
0
watashi blog.watashi.ws
2013 Multi-University Training Contest 9
...
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
A B C D E F G H I J Q&A
.
.
Boke and Tsukkomi
.
问题
.
.
..
.
.
.
.
找出所给一般图中一定不属于任何一个最大匹配的边。
首先计算一般图最大匹配数 c
枚举每条边,计算删去该边两个顶点后的最大匹配数
如果匹配数小于 c − 1,则说明该边不属于任何一个最大匹配
watashi blog.watashi.ws
2013 Multi-University Training Contest 9
...
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
...
.
.
.
..
.
.
.
..
.
.
.
A B C D E F G H I J Q&A
.
.
Boke and Tsukkomi
.
问题
.
.
..
.
.
.
.
找出所给一般图中一定不属于任何一个最大匹配的边。
首先计算一般图最大匹配数 c
枚举每条边,计算删去该边两个顶点后的最大匹配数
如果匹配数小于 c − 1,则说明该边不属于任何一个最大匹配
watashi blog.watashi.ws
2013 Multi-University Training Contest 9