【bzoj2893】征服王

2014年12月16日2,0260

Description

虽然春希将信息传递给了雪菜,但是雪菜却好像完全不认得春希了。心急如焚的春希打开了第二世代机能,对雪菜的脑内芯片进行了直连-hack。
进入到雪菜内部的春希发现(这什么玩意。。),雪菜的脑部结构被分成了n个块落,并且一些块落之间被有向边连接着。由于四分五裂的脑部,雪菜关于春希的记忆也完全消失,春希为了恋人,启动了inversionprocess.
在inversion process中,要想使雪菜回到正常状态,需要纳米机器人的帮助。纳米机器人可以从任意一个可以作为起点的块落出发进行修复,也可以在任意一个可以作为终点的块落结束修复(并不是到了某个终点就一定要停止)。春希希望所有的节点都能被修复(只要纳米机器人到过该点就算修复过),这样才能让雪菜重获新生。
作为纳米机器人1号的你能帮助春希算算至少需要多少个机器人才能拯救雪菜吗?
当然,如果无论如何都无法使得春希的愿望被满足的话,请输出”no solution”(不包括引号)

Input

题目包含多组数据
第1行有一个正整数t,表示数据的组数。
第2行有两个正整数n、m,a,b,分别表示块落的数量、有向边的数量、起点的数量、终点的数量。
第3行有a个正整数,表示可以作为起点的块落。
第4行有b个正整数,表示可以作为终点的块落。
第5行至第m+4行,每行有两个正整数u、v,表示能从编号为u的块落到编号为v的块落。
之后以此类推。

Output

输出共有t行,每行输出对应数据的答案。

Sample Input

2
2 1 1 1
1
2
2 1
3 2 3 3
1 2 3
1 2 3
1 2
1 3

Sample Output

no solution
2
【数据规模和约定】
对于30%的数据,满足n <= 10, m <= 100。
对于60%的数据,满足n <= 200, m <= 5000。
对于100%的数据,满足t<=10,n <= 1000, m <= 10000。

题解

orz zky

zky:

这题……一眼缩点,缩成DAG,然后问题就是限制起点终点的可重复经过的最小路径覆盖

神奇的费用流:

对于一个点u,拆成u->u’ ,连两条边,一条cap=1 cost=1,另一条cap=inf cost=0

s->u cap=inf cost=0,u’ -> t cap=inf cost=0

对于原图的边<u,v>:  u’->v cap=inf cost=0

跑最大费用流

有cost的边代表这个点经过一次

那么最大费用流每次会尽量走费用多的边,即走尽量多的点,正确性由网络流保证

增广次数即为答案

复杂度?

每次增广至少有1个cost,总共有n个cost,最坏增广n次

zky神犇告诉我,有向图60%的情况是缩成DAG

为何我从未做过这样的题