问题1495--基础匹配算法练习题

1495: 基础匹配算法练习题

时间限制: 10 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]
题目描述

小S最近学会了二分图匈牙利匹配算法。
现在二分图的X部有N个数字Ai,Y部有K个数字Ci 
已知如果Ai+Cj<=Z,那么Ai和Cj之间就有一条边,求二分图(X,E,Y)的最大匹配数。
小S是初学者.所以她想多做一些练习来巩固知识。于是她找到了一个长度为M的正整数数组B[],每次她会在B[]数组中抽取一段连续的区间[Li,Ri],把区间[Li,Ri]的所有数字作为二分图Y部的K个数字Ci.然后重新求一次二分图最大匹配数。
小S打算一共做Q次练习.但是她不知道每次计筧出的答案对不对.你能帮帮她吗?

输入

笫一行为三个正整数N、M、Z.
笫二行为N个正整数.笫i个正整数表示Ai。
笫三行力M个正整数,笫i个正整数表示Bi。
接下宋Q行每行两个正整数.笫i行的两个正整数分别表示Li、Ri。

输出

对十每次练习.输出该次练习的答案。

样例输入 Copy
4 10 8
1 2 4 6
6 3 6 2 8 4 9 10 6 8
4
1 4
2 5
5 6
1 6
样例输出 Copy
4
3
1
4
提示
【数据范围】
测试数据编号
N
M
Q
1-4
<50
<50
<50
5-10
<2501
<2501
<2501
11-14
< 152501
<45678
< 45678
15-16
<152501
<50
<52501
17-20
<152501
<52501
<52501


对于 100%的数据:1<=Ai、Bi、Z<=109,1<=Li<=Ri<=Q。

保证数据有一定梯度。

你可能潘要用到这些小S在学习匈牙利算法中査阅的资料:

【二分图】:

二分阁乂称作二部图,是图论中的一种特殊模型。设G = <V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(X.,Y), 并且图中的每条边(i,j)所关联的两个顶

点i和j分别属于这两个不同的顶点集(i∈X,j∈Y),则称图G为一个二分图。

【最大匹配】:

给定一个二分图G,在G的一个子图M中,M的边集中的任意两条边都不依附于同—个顶点,则称M是一个匹配。

选择这样的边数最大的子集称为图的最大匹配问题。

【增广路】:

若P是图G中一条连通两个未匹配顶点的路径.并且属M的边和不属M的边(即已匹配和待匹配的边〉在P上交替出现,则称P为相对于M的一条增广路径.

【匈牙利算法】:

用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出〉

算法轮廓:

⑴罝M为空。 

⑵找出一条增广路径P,通过取反操作获得更大的匹配M'代替M。

⑶重复⑵操作直到找不出增广路径为止。

来源/分类