当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6293:quailty算法

题目描述
二分图又称作二部图,是图论中的一种特殊模型。设$G=(V,E)$是一个无向图,如果点集合$V$可分割为两个互不相交的子集$A,B$,并且图中的每条边$(i,j)$所关联的两个顶点$i$和$j$分别属于这两个不同的顶点集$(i\in A,j\in B)$,则称图$G$为一个二分图。

一个"匹配"是指一组$E$的子边集$M$,满足$M$中任意两条边都没有公共顶点。"最大匹配"是指$M$中边数最多的一个匹配。"最小费用最大匹配"是指在边数最多的基础上,所选择的边的权值总和最小的匹配。

小T最近刚刚学会了二分图最大权匹配的KM(Kuhn-Munkres)算法,知道KM算法稍加修改就能计算二分图最小费用最大匹配。小T兴奋地把这个算法讲给小Q听,而小Q却吹牛说他自己发明了一个quailty算法,可以在低于线性的时空复杂度里求解二分图最小费用最大匹配。

小T不相信,于是给定$n$和一个长度为$n$的正整数数组$a_1,a_2,...,a_n$,写了一段代码根据$a[]$生成了一个很大的带权二分图,代码如下:

int ca = n;
long long cb = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j < i; j++){
cb++;
long long k = cb;
addedge(i, k, a[i] xor a[j]);
addedge(j, k, a[i] xor a[j]);
}

相关说明:
1. $ca$表示$A$中的点数,$cb$表示$B$中的点数,点都是从$1$开始连续编号的。
2. addedge(x,y,z)表示添加一条边权为$z$的无向边,两端点分别为$A$中的$x$点和$B$中的$y$点。
3. xor表示按位异或的运算符$\oplus$。按位异或的运算符是双目运算符,具有交换律,即$i\oplus j=j\oplus i$。按位异或可以理解成被运算的数字的二进制位对应位如果相同,则结果的该位置为0,否则为1,例如:$1(01)\oplus2(10)=3(11)$。按位异或还可以理解成参与运算的数字的每个二进制位都进行了不进位的加法,例如:$3(11)\oplus3(11)=0(00)$。

面对如此庞大的图,小Q自然不能算出来,于是他向你紧急求助。请写一个程序,求出最大匹配所需的最小费用。
输入解释
第一行包含一个正整数$T(1\leq T\leq 10)$,表示测试数据的组数。

每组数据第一行包含一个正整数$n(1\leq n\leq 300000)$。

第二行包含$n$个正整数$a_1,a_2,...,a_n(1\leq a_i\leq 10^9)$。
输出解释
对于每组数据,输出一行一个整数,即最大匹配所需的最小费用。
输入样例
2
3
8 2 5
5
9 3 5 7 1
输出样例
30
20
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6293

最后修改于 2020-10-25T23:30:02+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
4000/2000MS(Java/Others) 512000/512000K(Java/Others)