#BZOJ3776. 警察局
警察局
No submission language available for this problem.
题目描述
很久很久以前,朕拥有着S国的全部领土。S国由N个城市组成,而且某些城市有道路相连。不过,由于马车相向而行是非常危险的,所以道路都修成单向的。
朕决定在S国的若干不同城市设置警察局。不过由于特殊经济原因,朕只能建立恰好K个警察局。朕建立的警察局必须符合如下条件:
1、从每个没有警察局的城市出发,都能达到某个有警察局的城市。
2、任意城市一旦发生危险,总有警察局能够派出人员到达那个城市。
朕想知道一共有多少种不同的方案设置警察局(话说朕**是闲的么。。。)
输入格式
<p class="MsoNormal" style="text-indent:21.0pt;mso-layout-grid-align:none;
text-autospace:none">
</p>
每个测试点包含多组数据。
输入数据的第一行为C,为数据个数。
每组数据的第一行为N、M和K,代表了城市的个数、道路的个数以及建设的警察局数。以后M行,每行两个整数i、j,表示有一条从i城市到j城市的道路。输入数据没有重复道路。
输出格式
对每组数据输出一行,为建立K个警察局的不同方案数。
2 3 2 2 1 2 2 3 4 4 2 1 2 2 3 3 4 3 1
1
数据范围与约定
对于100%的数据,有1<=N<=100,1<=M<=20000,1<=K<=N,1<=C<=1400
Notice:此题从前那个加重复了,因而换成现在这个题,不好意思,浪费大家的提交了。