当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
6149：Valley Numer II
题目描述
众所周知，度度熊非常喜欢图。
它最近发现了图中也是可以出现 valley —— 山谷的，像下面这张图。
为了形成山谷，首先要将一个图的顶点标记为高点或者低点。标记完成后如果一个顶点三元组<X, Y, Z>中，X和Y之间有边，Y与Z之间也有边，同时X和Z是高点，Y是低点，那么它们就构成一个valley。
度度熊想知道一个无向图中最多可以构成多少个valley，一个顶点最多只能出现在一个valley中。
它最近发现了图中也是可以出现 valley —— 山谷的，像下面这张图。
为了形成山谷，首先要将一个图的顶点标记为高点或者低点。标记完成后如果一个顶点三元组<X, Y, Z>中，X和Y之间有边，Y与Z之间也有边，同时X和Z是高点，Y是低点，那么它们就构成一个valley。
度度熊想知道一个无向图中最多可以构成多少个valley，一个顶点最多只能出现在一个valley中。
输入解释
第一行为T，表示输入数据组数。
每组数据的第一行包含三个整数N，M，K，分别表示顶点个数，边的个数，标记为高点的顶点个数。
接着的M行，每行包含两个两个整数Xi，Yi，表示一条无向边。
最后一行包含K个整数Vi，表示这些点被标记为高点，其他点则都为低点。
● 1≤T≤20
● 1≤N≤30
● 1≤M≤N*(N-1)/2
● 0≤K≤min(N,15)
● 1≤Xi, Yi≤N, Xi!=Yi
● 1≤Vi≤N
每组数据的第一行包含三个整数N，M，K，分别表示顶点个数，边的个数，标记为高点的顶点个数。
接着的M行，每行包含两个两个整数Xi，Yi，表示一条无向边。
最后一行包含K个整数Vi，表示这些点被标记为高点，其他点则都为低点。
● 1≤T≤20
● 1≤N≤30
● 1≤M≤N*(N-1)/2
● 0≤K≤min(N,15)
● 1≤Xi, Yi≤N, Xi!=Yi
● 1≤Vi≤N
输出解释
对每组数据输出最多能构成的valley数目。
输入样例
3 3 2 2 1 2 1 3 2 3 3 2 2 1 2 1 3 1 2 7 6 5 1 2 1 3 1 4 2 3 2 6 2 7 3 4 5 6 7
输出样例
1 0 2
来自杭电HDUOJ的附加信息
| Recommend |
最后修改于 2020-10-25T23:28:48+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 12000/6000MS(Java/Others) | 32768/32768K(Java/Others) |
登陆或注册以提交代码