#P5875. 「2018 集训队互测 Day 4」小修和小栋生♂成树

    ID: 4876 传统题 1000ms 128MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS贪心带权拟阵交图论SPFA无向连通分量枚举与搜索路径恢复CF2900拟阵

「2018 集训队互测 Day 4」小修和小栋生♂成树

题目描述

小修正在和小栋一起造生成树。

他们各有一张 nn 个点,mm 条边的图。他们希望在图中找出一些边,使得只含有这些边的图是森林或者环套树森林。

由于小修和小栋是情侣,所以他们决定作出一样的选择,具体来说,对于第 ii 条边,两个人要么同时选择,要么同时不选择。

对于第 ii 条边有 aia_i 的权值,小修和小栋希望最终选择出来的边的权值和尽量大。

环套树森林中的每个连通分量至多含一个环,即每个连通分量是一棵树或一棵环套树。

输入格式

第一行包含两个整数 nn 和 mm,表示图的点数和边数。

接下来一行两个整数 type1,type2\text{type}_1,\text{type}_2,分别表示小修对最终图的要求和小栋的要求,当 type\text{type} 为 11 的时候,表示希望最后得到的是森林,如果 type\text{type} 为 22 则是环套树森林。

接下来 mm 行,每行 55 个整数 u1,i,v1,i,u2,i,v2,i,aiu_{1,i},v_{1,i},u_{2,i},v_{2,i},a_i,其中 u1,i,v1,iu_{1,i},v_{1,i} 表示这条边在小修的图中连接的点,u2,i,v2,iu_{2,i},v_{2,i} 表示在小栋的图中连接的点。

两张图都可能有重边和自环。

输出格式

输出一行一个整数,表示所选边的最大权值和。同一个编号的权值计一次。

样例 #1

样例输入 #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

样例输出 #1

4

数据范围与提示

对于所有数据,满足 1≤n,m≤300,1≤ai≤1051\le n,m\le 300,1\le a_i\le 10^5

以下限制如不做特殊说明均表示不超过。

子任务编号 nn mm 特殊限制 分数
1 300 300 u1,i=u2,i,v1,i=v2,iu_{1,i}=u_{2,i},v_{1,i}=v_{2,i} 3
2 20 无
3 7 300 type1=type2=1\text{type}_1=\text{type}_2=1 7
4 5 无 11
5 300 type1=type2=1\text{type}_1=\text{type}_2=1 15
6 type1=type2=2\text{type}_1=\text{type}_2=2 17
7 70 无 10
8 300 34