#1764. 小修和小栋生♂成树
小修和小栋生♂成树
小修和小栋生♂成树
题目描述
标题: 小修和小栋生♂成树 - Problem - QOJ.ac
#10371. 小修和小栋生♂成树
The problem was used in the following contests:
这不是一道提交答案题。
这不是一道交互题。
小修正在和小栋一起造生成树。
他们各有一张 n 个点,m 条边的图。他们希望在图中找出一些边,使得只含有这些边的图是森林或者环套树森林。
由于小修和小栋是情侣,所以他们决定作出一样的选择,具体来说,对于第 i 条边,两个人要么同时选择,要么同时不选择。
对于第 i 条边有 ai 的权值,小修和小栋希望最终选择出来的边的权值和尽量大。
这里环套树森林的定义指的是每个联通块都是树或者环套树。
输入格式
第一行包含两个整数 n 和 m,表示图的点数和边数。
接下来一行两个整数 type1,type2,分别表示小修对最终图的要求和小栋的要求,当 type 为 1 的时候,表示希望最后得到的是森林,如果 type 为 2 则是环套树森林。
接下来 m 行,每行 5 个整数 u1i,v1i,u2i,v2i,ai,其中 u1i,v1i 表示这条边在小修的图中连接的点,u2i,v2i 表示在小栋的图中连接的点。
数据不保证没有重边和自环。
输出格式
输出一行一个整数,表示最大的边权和。
样例数据
样例输入
6 5
1 1
1 2 1 2 1
2 3 2 3 1
3 4 3 4 1
1 4 5 6 1
5 6 1 4 1
样例输出
4
子任务
对于所有数据,满足 1≤n,m≤300,1≤ai≤105
以下限制如不做特殊说明均表示不超过。
子任务编号 n m 特殊限制 分数 1 300 300 u1i=u2i,v1i=v2i 3 2 20 无 3 3 7 300 type1=type2=1 7 4 5 无 11 5 300 type1=type2=1 15 6 17 7 70 70 无 10 8 300 300 34
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6 5
1 1
1 2 1 2 1
2 3 2 3 1
3 4 3 4 1
1 4 5 6 1
5 6 1 4 1
4