UOJ Logo Zijian Online Judge

ZOJ

Statistics

题目背景

小猫咪和小乌鸦是好朋友。

从很小很小的时候就是很好很好的好朋友。

小猫咪通过努力,最终在某个领域取得突破,并获得了"火车"的荣誉称号。

小乌鸦笨笨的。

然而有一天,一个自称是神明的家伙说要推动什么工业革命,给小乌鸦叫了一份"八什么鸟套餐"的外卖什么的。小乌鸦吃完了就精通核物理了。这种事绝对很奇怪啊。

小猫咪自然为小乌鸦感到高兴,但是心里也觉得不是很舒服,并且担心这份外卖里面是不是有一些奇怪的食品添加剂,会不会有副作用什么的。

虽然学的专业和核物理半毛钱关系没有,她还是决定依照自己的理论试一试...

题目描述

这份外卖的样本里面含有 $n$ 种α-基团, $m$ 种β-基团,每种基团的数量未知。根据她的理论,这里面一共存在 $k$ 条"联系",每条"联系"可以看做是一种α-基团和一种β-基团所构成的无序对。正是这些"联系"为小乌鸦提供了技术支持。

每条"联系"形如 $(i,j,l,r)$ ,设 $i$ 号α-基团的数量 + $j$ 号β-基团的数量为 $A(i,j)$,要求满足 $l \leq A(i,j) \leq r$ ,且每种基团的数量为非负整数$④$。

求满足所有联系的情况下,α-基团总数 - β-基团总数的最大值。

一句话题意:给定一个n+m个点k条边的二分图,现在让你给每个点赋点权(为非负整数),且第i条边上的两个点点权和在[li,ri]之间。求二分图第一部分的点权和减去第二部分的点权和的最大值。 二分图第一部分对应所有α-基团 第二部分对应所有β-基团 边对应所有联系

输入格式

第一行包括三个整数 $n$ , $m$ , $k$ 。

接下来k行,每行4个整数 $i$ , $j$ , $l$ , $r$ ,用于描述一种联系。

输出格式

第一行包括一个整数,表示你求出的最大值。

样例一

input

5 5 10
1 1 3 5
1 2 3 5
2 2 4 7
2 3 4 7
3 3 3 6
3 4 3 5
4 4 2 4
4 5 3 6
5 5 4 7
5 1 3 6

output

27

样例二

见样例数据下载

限制与约定

每个数据点的约定如下:

对于第$1$个测试点,$n,m \leq 5$,$k \leq 25$,$l \leq r \leq 10$,保证图联通$⑤$

对于第$2$个测试点,$n,m \leq 100$,$k \leq 2000$,$l = r \leq 200$,保证图联通

对于第$3-5$个测试点,$n,m \leq 100$,$k \leq 2000$,$l \leq r \leq 200$

对于第$6$个测试点,$n,m \leq 50000$,$k \leq 200000$,$l = r \leq 10^9$,保证图联通

对于第$7-10$个测试点,$n,m \leq 50000$,$k \leq 200000$,$l \leq r \leq 10^9$

对于所有数据,保证每种基团都存在至少一种与其他离子的"联系",不存在两种"联系"使得它们所联系的基团无序对相同$①$。保证所求的最大值存在。$②$$③$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

补充说明

$①$:无重边。

$②$:小乌鸦生命力旺盛,你并不用担心她是否会被毒死。

$③$:小猫咪真的不是学民科专业的,只是出题人比较词穷,不知道怎么把她的理论用通俗易懂的语言讲述出来。

$④$:可以为0。

$⑤$:把基团看作点,联系看作边,对应的图联通。

下载

样例数据下载