投稿
  1. 高性能架构探索首页
  2. C/C++

关于最大匹配，最小点覆盖，最少路径覆盖和最大独立集的总结

admin • • C/C++ • 阅读 316

(1)二分图的最大匹配

匈牙利算法

(2)二分图的最小点覆盖

二分图的最小点覆盖=二分图的最大匹配

求最小点覆盖：从右边所有没有匹配过的点出发，按照增广路的“交替出现”的要求DFS。最终右边没有访问过的点和左边访问过的点组成最小点覆盖。

证明见这里

(3)二分图的最少边覆盖

二分图的最少边覆盖=点数-二分图的最大匹配

证明：

先贪心选一组最大匹配的边放进集合，对于剩下的没有匹配的点，随便选一条与之关联的边放进集合，那么得到的集合就是最小边覆盖。

所以有：最小边覆盖=最大匹配+点数-2*最大匹配=点数-最大匹配

(4)二分图的最大独立集

二分图的最大独立集=点数-二分图的最大匹配

证明：

我们可以这样想，先把所有的点放进集合，然后删去最少的点和与之相关联的边，使得全部边都被删完，这就是最小点覆盖。所以有：最大独立集=点数-最小点覆盖

(5)有向无环图的最少不相交路径覆盖

我们把原图中的点$V$拆成两个点$Vx$和$Vy$，对于原图中的边$A->B$，我们在新图中连$Ax->By$。那么最少不相交路径覆盖=原图的点数-新图的最大匹配

证明：

一开始每个点都独立为一条路径，在二分图中连边就是将路径合并，每连一条边路径数就减一。因为路径不能相交，所以不能有公共点，这恰好就是匹配的定义。所以有：最少不相交路径覆盖=原图的点数-新图的最大匹配

友情题：

bzoj1143[CTSC2008]祭祀river

(6)有向无环图的最少可相交路径覆盖

先用floyd求出原图的传递闭包， 如果a到b有路， 那么就加边a->b。 然后就转化成了最少不相交路径覆盖问题。

(7)有向无环图中最少不相交路径覆盖和最大独立集的相互转化

用偏序集，一般可以抽象为有向无环图。建议先看看这篇博客

Dilworth定理：有向无环图的最大独立集=有向无环图最少不相交路径覆盖

友情题

hdu3335

裸的偏序集。

注意要去重，因为要保证是有向无环图。
关于最大匹配，最小点覆盖，最少路径覆盖和最大独立集的总结关于最大匹配，最小点覆盖，最少路径覆盖和最大独立集的总结

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj

using namespace std;

typedef long long LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP;

#define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define fill(a,l,r,v) fill(a+l,a+r+1,v)
#define re(i,a,b)  for(i=(a);i<=(b);i++)
#define red(i,a,b) for(i=(a);i>=(b);i--)
#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define p_b(a) push_back(a)
#define SF scanf
#define PF printf
#define two(k) (1<<(k))

template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;}

inline int sgn(DB x){if(abs(x)<1e-9)return 0;return(x>0)?1:-1;}
const DB Pi=acos(-1.0);

int gint()
  {
        int res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
        if(z==EOF)return 0;
        if(z=='-'){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());
        return (neg)?-res:res; 
    }
LL gll()
  {
      LL res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
        if(z==EOF)return 0;
        if(z=='-'){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());
        return (neg)?-res:res; 
    }

const int maxn=1000;

int n;
LL a[maxn+10];

int now,info[maxn+10];
struct Tedge{int v,next;}edge[maxn*maxn+100];

void addedge(int u,int v){now++;edge[now].v=v;edge[now].next=info[u];info[u]=now;}

int vis[maxn+10],match[maxn+10];
int ans;

int find(int u)
  {
      for(int i=info[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)
          if(!vis[v])
              {
                  vis[v]=1;
                  if(match[v]==-1 || find(match[v]))
                      {
                          match[v]=u;
                          return 1;
                        }
                    }
        return 0;
    }

int main()
  {
      freopen("hdu3335.in","r",stdin);
      freopen("hdu3335.out","w",stdout);
      int i,j;
      for(int Case=gint();Case;Case--)
        {
            n=gint();
            re(i,1,n)a[i]=gll();
            sort(a+1,a+n+1);
            n=unique(a+1,a+n+1)-a-1;
            now=-1;mmst(info,-1);
            re(i,1,n)re(j,1,n)if(i!=j && a[i]%a[j]==0)addedge(i,j);
            ans=0;
            mmst(match,-1);
            re(i,1,n){mmst(vis,0);ans+=find(i);}
                cout<<n-ans<<endl;
        }
      return 0;
  }

View Code
poj1065

我们把木棍$i$看成一个二元组$(L_i,W_i)$

定义偏序关系$(L_i,W_i)leq (L_j,W_j)Leftrightarrow L_ileq L_j 且 W_ileq W_j$

我们先构建一个有向无环图。

我们求的就是最少不相交路径覆盖。

考虑一个独立集，我们发现有以下的性质：

（1）对于$(L_i,W_i)$和$(L_j,W_j)$，$L_i$一定不等于$L_j$，$W_i$一定不等于$W_j$；

（2）如果按$L$严格递增排序，那么$W$一定严格递减。

很好，我们首先将所有的二元组$(L,W)$按$L$从小到大排序，如果$L$相同，那么按$W$从小到大排序。

那么一个独立集等价于一个严格递减子序列；一条路径等价于一个非严格递增子序列。

根据Dilworth定理，有2种方法：

（1）求最大独立集，即求最长严格递减子序列,用DP可以在$O(N^2)$内完成，优化一下还能做到$O(Nlog_{2}N)$。

（2）直接求最少不相交路径覆盖，即至少用多少个非严格递增子序列能覆盖完原序列，用贪心可以在$O(N^2)$内完成，优化一下还能做到$O(Nlog_{2}N)$。

根据Dilworth定理，这两种方法都是对的。

我的程序是用直接求最少不相交路径覆盖：
关于最大匹配，最小点覆盖，最少路径覆盖和最大独立集的总结关于最大匹配，最小点覆盖，最少路径覆盖和最大独立集的总结

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj

using namespace std;

typedef long long LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP;

#define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define fill(a,l,r,v) fill(a+l,a+r+1,v)
#define re(i,a,b)  for(i=(a);i<=(b);i++)
#define red(i,a,b) for(i=(a);i>=(b);i--)
#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define p_b(a) push_back(a)
#define SF scanf
#define PF printf
#define two(k) (1<<(k))

template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;}

inline int sgn(DB x){if(abs(x)<1e-9)return 0;return(x>0)?1:-1;}
const DB Pi=acos(-1.0);

int gint()
  {
        int res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
        if(z==EOF)return 0;
        if(z=='-'){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());
        return (neg)?-res:res; 
    }
LL gll()
  {
      LL res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
        if(z==EOF)return 0;
        if(z=='-'){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());
        return (neg)?-res:res; 
    }

const int maxn=5000;

bool cmp(PII a,PII b){return (a.fi==b.fi)?a.se<b.se:a.fi<b.fi;}

int n;
PII d[maxn+100];
int t[maxn+100];

int main()
  {
      freopen("poj1065.in","r",stdin);
      freopen("poj1065.out","w",stdout);
      int i,j;
      for(int Case=gint();Case;Case--)
        {
            n=gint();
            re(i,1,n)d[i].fi=gint(),d[i].se=gint();
            sort(d+1,d+n+1,cmp);
            int num=0;
            re(i,1,n)
              {
                  int flag=0;
                  re(j,1,num)if(d[i].se>=t[j]){t[j]=d[i].se;flag=1;break;}
                  if(!flag)t[++num]=d[i].se;
              }
            cout<<num<<endl;
        }
      return 0;
  }

View Code
bzoj3997[TJOI2015]组合数学

(8)二分图的带权最大匹配

KM算法。

原文链接: https://www.cnblogs.com/maijing/p/4844893.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/222401

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月13日 上午11:43
下一篇 2023年2月13日 上午11:44

相关推荐