「THUPC 2021 初赛」独立
题目描述
给定一张 n 个点 m 条边的无向图。
对于 {1,2,…,n} 的某个子集 A,A 的分数为:
- 初始分数为 0;
- 对于所有 i∈A,分数加 ai;
- 对于所有边 (u,v,k)(代表从 u 到 v 值为 k 的边)满足 u∈A 并且 v∈A,分数减 k;
现在请你计算出所有的 A 中,分数最高是多少。
输入格式
令 q=101,b=137,p=1,000,000,007。
第一行包含六个整数 n,m,x0,y0,a0,z0(1≤n≤100000,0≤m≤2n,0≤x0,y0,a0,z0<p)。
对于 1≤i≤n,有 ai=(q×ai−1+b)modp。
对于 1≤i≤m, 有 xi=(q×xi−1+b)modp,yi=(q×yi−1+b)modp,zi=(q×zi−1+b)modp。对于每一组 (xi,yi,zi) 描述了一条连接 (ximodn)+1,(yimodn)+1 的值为 zi 的边,先令 ui=(ximodn)+1、vi=(yimodn)+1。若 ui=vi,或者此前已经保留过连接这两个端点的无向边(不区分端点顺序),则忽略本次生成的边。
所有递推仍严格进行 m 次,被忽略的边不补生成;最终保留的边数可以少于 m。子集 A 可以为空,答案为最高分的普通整数值,不取模。
输出格式
输出一行一个整数表示最高分数。
样例输入 1
10 5 1 2 3 4
样例输出 1
3909327860