http://blog.csdn.net/whosemario/article/details/8513836
http://blog.csdn.net/fenggaoyuehei/article/details/6034535
http://blog.csdn.net/leolin_/article/details/7199688
题目构造数学模型很简单,每一个集合看成一个点,如果两个集合中有相同的数字,则这两个集合对应的点相连接。最后会构成一个无向图,我们就是要求这个图的最大独立集。要求一个图的最大独立集就是求其补图的最大团。
最大团
这里介绍一下最大团
给定一个无向图G=(V,E),如果U属于E,且任意(u,v)属于U,且同时又属于E,则称U是G的完全子图。 G的完全子图U是G的最大团当且仅当U不包含在G的更大的完全子图中,即U就是最大的完全子图。
如下图:
此图的最大团有:
那怎样求一个图的呢?朴素的搜索将会是n*2^n的时间复杂度,所以需要进行剪枝,并记录一些状态,即DP+DFS的思想。先把代码写出来。
#define SIZE 102
int mat[SIZE][SIZE]; /*图矩阵*/
int dp[SIZE];
int mx;
int stack[SIZE][SIZE];
void dfs(int N,int num,int step){
if(num==0){
if(step > mx){
mx=step;
}
return ;
}
for(int i=0;i<num;i++){
int k = stack[step][i];
if(step+N-k<=mx) return ;
if(step+dp[k]<=mx) return ;
int cnt = 0;
for(int j=i+1;j<num;j++)
if(mat[k][stack[step][j]]){
stack[step+1][cnt++]=stack[step][j];
}
dfs(N,cnt,step+1);
}
}
void run(int N){
mx =0;
for(int i=N-1;i>=0;i--){
int sz =0;
for(int j=i+1;j<N;j++)
if(mat[i][j]) stack[1][sz++]=j;
dfs(N,sz,1);
dp[i]=mx;
}
}
下面简单地说一下思路(节点下标是从0开始的):
dp[i]表示从i到n-1中的最大团的节点数。
枚举每一个节点,看这个节点与哪些编号大于它的节点相连,记录这些节点,然后递归地处理这些节点。。。
怎样去做剪枝那?
假如已经到x个节点在“团”里的状态,处理到了第k个节点,判断
x+n-k <= mx
和
x+dp[k] <= mx
两个条件。只要有一个成立,则没有必要继续下去了。
最大独立集
最大独立集就是其补图的最大团
poj1419是一个很直白的求最大独立集的问题,可以试着做做
二分图的最大独立集
如果一个图是二分图,那么它的最大独立集就是多项式时间可以解决的问题了 |最大独立集| = |V|-|最大匹配数|
证明:
设最大独立集数为U,最大匹配数为M,M覆盖的顶点集合为EM。
为了证明|U|=|V|-|M|,我们分两步证明|U|<=|V|-|M|和|U|>=|V|-|M|
1 先证明 |U|<=|V|-|M|
M中的两个端点是连接的,所有M中必有一个点不在|U|集合中,所以|M|<=|V|-|U|
2 再证明|U|>=|V|-|M|
假设(x,y)属于M
首先我们知道一定有|U|>=|V|-|EM|,那么我们将M集合中的一个端点放入U中可以吗?
假设存在(a,x),(b,y),(a,b)不在EM集合中
如果(a,b)连接,则有一个更大的匹配存在,矛盾
如果(a,b)不连接,a->x->y->b有一个新的增广路,因此有一个更大的匹配,矛盾
所以我们可以了解到取M中的一个端点放入U中肯定不会和U中的任何一个点相连,所以|U|>=|V|-|EM|+|M|=|V|-|M|
所以,|U|=|V|-|M|
二分图的最小顶点覆盖
定义:
寻找一个点集,使得图上任意一条边至少一个端点位于这个点集内部。二分图的|最小点集|=|最大匹配|
证明:
按照定义所说,就是最大匹配中的每个匹配的一个节点就是最小点集。
如果有一条边的两个端点都不在EM中,那最大匹配就会变成|M|+1,产生矛盾。所以又|最小点集|<=|最大匹配|
我们现在只看最大匹配M,如果最小点集小于M,那么肯定有边无法涉及到,因此|最小点集|>=|最大匹配|
所以有|最小点集|=|最大匹配|
对于一个一般图是NP Hard的问题,对于二分图可能就是多项式可解的问题咯
最小路径覆盖
定义:
一个有向无环图,要求用尽量少的不相交的简单路径覆盖所有的节点。
构图:
建立一个二分图,把原图中的所有节点分成两份(X集合为i,Y集合为i'),如果原来图中有i->j的有向边,则在二分图中建立i->j'的有向边。最终|最小路径覆盖|=|V|-|M|
证明:
上图中,对应左边的DAG构造了右边的二分图,可以找到二分图的一个最大匹配M:1->3' 3->4',那么M重的这两条匹配边怎样对应DAG中的路径的边呢?
使二分图的一条边对应于DAG中的一条有向边:1->3'对应于左图的1->3,这样DAG中的1就有一个后继结点(3回事1的唯一后继结点,因为二分图中的一个顶点之多关联一条边!),所以1不会成为DAG中的一条路径中的结尾顶点,同样,3->4'对应于左图的3->4,3也不会成为结尾顶点,那么原图中总共有4个顶点,减去2个有后继的顶点,还有两个顶点,即DAG路径的结尾顶点,每个即为顶点对应一个路径。二分图中寻找最大匹配M,就是找到了对应DAG中的非路径结尾顶点的最大数目,那么DAG中|V|-|M|就是DAG中结尾顶点的最小数目,即DAG的最小路径数目。
下面写一个二分图匹配的递归方法的代码:
#define SIZE 100
int mat[SIZE][SIZE]; /*图矩阵*/
int match1[SIZE];
int match2[SIZE];
int color[SIZE];
bool dfs(int N,int u){
for(int i=0;i<N;i++)
if(mat[u][i] && color[i]){
color[i]=1;
if(match2[i]==-1){
match2[i]=u;
match1[u]=i;
return true;
}
else{
bool flag = dfs(N,match2[i]);
if(flag){
match2[i]=u;
match1[u]=i;
return true;
}
}
}
return false;
}
int maxMatch(int N){
memset(match1,-1,sizeof(match1));
memset(match2,-1,sizeof(match2));
for(int i=0;i<N;i++){
memset(color,0,sizeof(color));
dfs(N,i);
}
int ret = 0;
for(int i=0;i<N;i++)
if(match1[i]!=-1) ++ret;
return ret;
}
再写一个二分图最大匹配的非递归方法:
#define SIZE 100
int mat[SIZE][SIZE]; /*图矩阵*/
int match1[SIZE];
int match2[SIZE];
int queue[SIZE];
int head,tail;
int pre[SIZE];
int maxMatch(int N){
int ret = 0;
memset(match1,-1,sizeof(match1));
memset(match2,-1,sizeof(match2));
for(int i=0;i<N;i++){
memset(pre,-1,sizeof(pre));
head = tail = 0;
queue[tail++] = i;
while(head < tail && match1[i]==-1){
int u = queue[head++];
for(int j =0;j<N&&match1[i]==-1;j++)
if(mat[u][j] && pre[j]==-1){
queue[tail++] = match2[j];
pre[j]=u;
if(queue[tail-1]<0){
for(int t=j,k=0;t>=0;j=t){
match2[j]=k=pre[j];
t=match1[k];
match1[k]=j;
}
}
}
}
}
}
1.独立集:任意两点都不相连的顶点的集合
2.定理:最大独立集=顶点数-最大匹配边
3.完全子图:任意两点都相连的顶点的集合(最大完全子图即最大团)
4.定理:最大团=原图补图的最大独立集=顶点数-最大匹配数
注意,要反向建图(把认识的变成不认识的,不认识的成为认识的,这样才能求补图)
求二分图最大匹配(指派问题)的匈牙利算法:
谈匈牙利算法自然避不开Hall定理,即是:对于二部图G,存在一个匹配M,
使得X的所有顶点关于M饱和的充要条件是:对于X的任意一个子集A,和A邻接的点集为T(A),恒有: |T(A)| > = |A|
匈牙利算法是基于Hall定理中充分性证明的思想,其基本步骤为:
1.任给初始匹配M;
2.若X已饱和则结束,否则进行第3步;
3.在X中找到一个非饱和顶点x0,作V1 ← {x0}, V2 ← Φ;
4.若T(V1) = V2则因为无法匹配而停止,否则任选一点y ∈T(V1)/V2;
5.若y已饱和则转6,否则做一条从x0 →y的可增广道路P,M←M⊕E(P),转2;
6.由于y已饱和,所以M中有一条边(y,z),作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}, 转4;
来自:http://www.csdn.net/develop/Article/19/19501.shtm
二分图的最大匹配匈牙利算法
#include <fstream.h>
#include <string.h>
#define maxn 105
int nx,ny,jobnum;
int g[maxn][maxn];//邻接矩阵
int ans;
int sx[maxn],sy[maxn]
int cx[maxn],cy[maxn];//X集v点匹配Y集u点,则有:cx[v]=u,cx[u]=v
int path(int u)
{
sx[u]=1;
int v,i;
for(v=1;v <=ny;v++)
if( (g[u][v]> 0) && (!sy[v]) )
{
sy[v]=1;
if( (!cy[v]) || (path(cy[v])) )
{
cx[u]=v;
cy[v]=u;
return 1;
}
}
return 0;
}
int solve()
{
ans=0;
int i,j;
memset(cx,0,sizeof(cx));
memset(cy,0,sizeof(cy));
for(i=1;i <=nx;i++)
if(!cx[i])
{
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
ans+=path(i);
}
return 0;
}
int main()
{
ifstream cin( "1364.in ");
ofstream cout( "1364.out ");
int i,j,k,l;
while(cin> > nx,nx> 0)
{
cin> > ny> > jobnum;
if(cin.fail())
return 0;
memset(g,0,sizeof(g));
for(k=0;k <jobnum;k++)
{
cin> > l> > i> > j;
g[i][j]=1;
}
solve();
cout < <ans < <endl;
}
return 0;
}
最小支配集
顶点集D是图G=(V,E)的支配集当且仅当对任意u∈V-D存在v∈D使(u,v)∈E.最小支配集问题是对给定图G找出使|D|最小的支配集D.当所给的图是一棵树T时,我们可以利用树的前序标号表示法设计出求最小支配集D的线性时间算法如下:
MIN-DOMINATE-SET(T)
begin
for i:=1 to ndo
cover[i]:=0;
D:=;
for i:=ndownto 2 do
if cover[i]=0 then
begin
D:=D∪{parent[i]};
cover[parent[i]]:=1;
cover[parent[parent[i]]]:=1
end
end;{MIN-DOMINATE-SET}
最小支配集问题同样具有贪心选择性质和最优子结构性质,从而保证了算法MIN-DOMINATE-SET的正确性,算法所需的计算时间也是O(n).
来自:http://topic.csdn.net/u/20080928/14/4e7a079c-21c4-484b-ab80-3785beccd489.htm