二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。在这个基础上,把每个点赋予一个非负的权值,这两个问题就转化为:二分图最小点权覆盖和二分图最大点权独立集。
二分图最小点权覆盖
从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。
建模:
原二分图中的边(u,v)替换为容量为INF的有向边(u,v),设立源点s和汇点t,将s和x集合中的点相连,容量为该点的权值;将y中的点同t相连,容量为该点的权值。在新图上求最大流,最大流量即为最小点权覆盖的权值和。
二分图最大点权独立集
在二分图中找到权值和最大的点集,使得它们之间两两没有边。其实它是最小点权覆盖的对偶问题。答案=总权值-最小点覆盖集。具体证明参考胡波涛的论文。
例:HDU1569
题意:一个m*n的棋盘,每个格子都有一个权值,从中取出某些数,使得任意两个数所在的格子没有公共边,并且所取去出的数和最大。求这个最大的值。
解:
将格子染色成二分图,显然是求二分图的最大点权独立集。将问题转化为二分图最小点权覆盖来求解,最终结果=总权和-最大流。
/*
最大点权独立集:
转化为最小点权覆盖问题,最大点权独立集=总权值-最小点权覆盖集
最小点权覆盖:
设立源点s和t,s连边到点i,容量为i点的权值;点j连边到t,容量为j点权值;原二分图中的边容量为INF,求最大流即为最小点权覆盖。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int maxv = 2600;
const int maxe = 1000000;
int n,m;
int g[55][55];
struct Edge
{
int v;
int next;
int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];
int start,end;
void addEdge(int a,int b,int c)
{
e[edgeNum].v = b;
e[edgeNum].flow = c;
e[edgeNum].next = head[a];
head[a] = edgeNum++;
e[edgeNum].v = a;
e[edgeNum].flow = 0;
e[edgeNum].next = head[b];
head[b] = edgeNum++;
}
void Init()
{
edgeNum = 0;
memset(head,-1,sizeof(head));
memset(d,0,sizeof(d));
}
int sap(int s,int t,int n) //源点,汇点,结点总数
{
int i,x,y;
int f,ans = 0;
for(i = 0; i < n; i++)
now[i] = head[i];
vh[0] = n;
x = s;
while(d[s] < n)
{
for(i = now[x]; i != -1; i = e[i].next)
if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
break;
if(i != -1)
{
now[x] = preh[y] = i;
pre[y] = x;
if((x=y) == t)
{
for(f = INF,i=t; i != s; i = pre[i])
if(e[preh[i]].flow < f)
f = e[preh[i]].flow;
ans += f;
do
{
e[preh[x]].flow -= f;
e[preh[x]^1].flow += f;
x = pre[x];
}while(x!=s);
}
}
else
{
if(!--vh[d[x]])
break;
d[x] = n;
for(i=now[x]=head[x]; i != -1; i = e[i].next)
{
if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
{
now[x] = i;
d[x] = d[e[i].v] + 1;
}
}
++vh[d[x]];
if(x != s)
x = pre[x];
}
}
return ans;
}
void build()
{
int i,j;
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
int t = (i-1)*n+j;
if((i+j)%2)
{
addEdge(start,t,g[i][j]);
if(i>1)
addEdge(t,t-n,INF);
if(i<m)
addEdge(t,t+n,INF);
if(j>1)
addEdge(t,t-1,INF);
if(j<n)
addEdge(t,t+1,INF);
}
else
addEdge(t,end,g[i][j]);
}
}
}
int main()
{
int i,j;
int result;
while(scanf("%d %d",&m,&n) != EOF)
{
result = 0;
Init();
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%d",&g[i][j]);
result += g[i][j];
}
}
start = 0;
end = n*m + 1;
build();
printf("%d\n",result-sap(start,end,end+1));
}
return 0;
}
分享到:
相关推荐
运用MATLAB找出最大独立集和最小点覆盖。先用反圈法求二部图的最大匹配。
9 方格取数问题 二分图点权最大独立集 网络最小割 10 餐巾计划问题 线性规划网络优化 最小费用最大流 11 航空路线问题 最长不相交路径 最小费用最大流 12 软件补丁问题 最小转移代价 最短路径 13 星际转移问题 网络...
针对图论中最大独立集问题设计了一个分支降阶算法,并通过增加快速降阶规则来降低算法的时间复杂度,最终通过分析得出一个时间复杂度为[O(1.285n)]的精确算法,该算法在理论上得到了一般图的最大独立集的最优解。
图论解决系统稳定性,最大独立集,最大团问题,以及和图的着色问题类似。
d-无爪图中最大权独立集问题的一种改进逼近算法_An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs.pdf
针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集。首先构造了一个二分图,并通过该图找出皇冠结构,采用皇冠分解技术分解图,针对无皇冠的子图设计了一个分支降阶递归算法,然后...
独立集是指图 G 中两两互不相邻的顶点构成的集合。任意有关图中团的性质都能很自然的转述成独立...一般而言,寻找图的最大团是 NP 困难的,从而寻找图的最大独立集也是 NP 困难的。用模拟退火算法找出图的最大独立集。
图论- DAG 的覆盖与独立集.rar
网络流ppt,最小点覆盖,König定理:二分图中的最大匹配数=这个图中的最小点覆盖数,König定理证明,最小点覆盖构造
ACM模板,主要包括图论,字符串,数据结构等模板,例如 图论 1.1 网络流 1.1.1 最大流 1.1.1.1 算法模板 ...1.1.2.5 最小点权覆盖集 1.1.2.6 最大点权独立集 1.1.2.7 建图实战 1.1.3 费用流 1.1.3.1 算法模板 等
基于最大权重独立集的D2D资源分配研究,王明昕,彭涛,密集和复杂的场景下,一种更为灵活的频谱资源利用方式被认为可以满足日益增长的传输需求。D2D通信(设备与设备间通信)便是在这种
最大独立集是一个独立集,不是任何其他独立集的适当子集。 如果存在一个顶点x∈V(G)使得G − x为a,则顶点集合为V(G)的连通图G(称为图)称为拟树图(称为拟林图)。树(分别是森林)。 在本文中,我们调查了...
计算机网络课程设计-- 小型网络设计 课程设计说明书 NO.1 " 小型网络设计 " "1、课程设计的目的 " "通过对网络的具体规划和组建,掌握网络互连设备的使用及工作原理;掌握IP地址" "的配置及数据传输过程和路由的选择...
实验4:双端口存储器实验 ----独立方式.pdf实验4:双端口存储器实验 ----独立方式.pdf实验4:双端口存储器实验 ----独立方式.pdf实验4:双端口存储器实验 ----独立方式.pdf实验4:双端口存储器实验 ----独立方式.pdf...
.设计了一种基于目标区域Voronoi划分的集中式近似算法CVT,用于计算完全覆盖目标区域所需要的近似最小节点集....理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面 都优于已有的贪婪算法.
支配集覆盖集独立集与匹配讲义PPT课件.pptx
一个求解简单超图中最大独立集的算法.pdf
支配集覆盖集独立集与匹配讲义学习教案.pptx
支配集覆盖集独立集与匹配讲义PPT学习教案.pptx