精华内容
下载资源
问答
  • 最小点覆盖

    千次阅读 2016-08-07 19:47:23
    最小点覆盖为:在一个二分图中,选取最少的点可以把所有的变覆盖, 点的最少个数就是最小点覆盖最小点覆盖=最大二分匹配。 克鲁斯卡尔算法。 关于本题: £:把从零开始,转化成从一开始。 £:起点不用...

    题目连接

    /*
        最小点覆盖为:在一个二分图中,选取最少的点可以把所有的变覆盖,
        点的最少个数就是最小点覆盖。
        最小点覆盖=最大二分匹配。
        克鲁斯卡尔算法。
        关于本题:
        £:把从零开始,转化成从一开始。
        £:起点不用加入E[],因为机器的起始状态就是1,或者加入E[]但是不参加计算,(我采用的是第二种。)
    */
    #include<cstdio>
    #include<cstring>
    #include<map>
    #include<vector>
    #include<cstring>
    #include<iostream>
    using namespace std;
    const int maxn=100+50;
    int k,n,m;
    vector<int>E[maxn];
    int f[maxn];
    bool vis[maxn];
    int ans;
    bool match(int x)
    {
        int l=(int)E[x].size();
        for(int i=0;i<l;i++)
        {
            int t=E[x][i];
            if(!vis[t])
            {
                vis[t]=true;
                if(f[t]==-1||match(f[t]))
                {
                    f[t]=x;
                    return true;
                }
            }
        }
        return false;
    }
    int hungary()
    {
        ans=0;
        memset(f,-1,sizeof(f));
        for (int i=2;i<=n;i++)
        {
            memset(vis, false, sizeof(vis));
            if(match(i))
                ans++;
        }
        return ans;
    }
    int main ()
    {
        while(scanf("%d",&n),n)
        {
            scanf("%d%d",&m,&k);
            int I,a,b;
            for(int i=0;i<=n;i++)
                E[i].clear();
            for(int i=0;i<k;i++)
            {
                scanf("%d%d%d",&I,&a,&b);
                E[a+1].push_back(b+1);
            }
            int ans=hungary();
            printf("%d\n",ans);
        }
        return 0;
    }
    展开全文
  • 如果没有申明是什么图默认是二分图最小点覆盖:点覆盖的概念定义: 对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。最小点覆盖:就是中点的个数最少的S集合。 普通图的最小点覆盖数...

    如果没有申明是什么图默认是二分图

    最小点覆盖:

    点覆盖的概念定义
    对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。

    最小点覆盖:就是中点的个数最少的S集合。
    普通图的最小点覆盖数好像只能用搜索解,没有什么比较好的方法(可能我比较弱。。)所以在此只讨论二分图的最小点覆盖的求法

    结论: 二分图的最小点覆盖数=该二分图的最大匹配数,具体证明的方法看大佬博客,里面还给出了如何求具体的最小覆盖的点是哪些点。

    最小边覆盖:

    边覆盖的概念定义:
    边覆盖是图的一个边子集,使该图上每一节点都与这个边子集中的一条边关联,只有含孤立点的图没有边覆盖,边覆盖也称为边覆盖集,图G的最小边覆盖就是指边数最少的覆盖,图G的最小边覆盖的边数称为G的边覆盖数。

    普通图 的最小边覆盖好像也没有什么除了暴力好的解法,自己菜(逃

    结论: 二分图的最小边覆盖数=图中的顶点数-(最小点覆盖数)该二分图的最大匹配数

    最大匹配:

    匹配:在图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点。

    最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。

    算法: 匈牙利算法求二分图的最大匹配

    最小路径覆盖:

    DAG图的最小路径覆盖可以转化为二分图的人后求解直接上大佬的博客吧反正让我讲也讲不出什么花来,我只是整合一下,学起来比较系统。

    还有无向图的最小路径覆盖,找了很多资料都没有找到合适的解释,这里有一篇博客提到了,但是没有找到其他的资料证明他的正确性,严重的颠覆了我的认知。

    最大独立集:

    最大独立集:在N个点的图G中选出m个点,使这m个点两两之间没有边的点中,m的最大值。
    结论: 二分图的最大点独立数=点的个数-最小点覆盖数(最大匹配)
    证明: 除过最小点覆盖集,剩下的点全部都是互相独立的,因为它们任意两个点之间都没有直接的连边。
    我们用反证法来证明一下,设最小点覆盖集为V,假如有两个没在V中的点之间有一条边,那么这条边就不会被V中的点所覆盖,那么V就不是
    最小点覆盖集,又因为V是最小点覆盖集,所以刚才假设的两个点时不存在的,座椅,除过V之外的点都是两两相互独立的。

    展开全文
  • 前言: ...点覆盖、最小点覆盖 点覆盖集即一个点集,使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。。极小点覆盖(minimal vertex covering):本身为点覆盖,其真子集都不是

    转载请注明出处(别管写的好坏,码字也不容易):http://blog.csdn.net/hitwhacmer1

    前言:

            有自己写的,有摘的别人的,前面是摘的,也是无心整理,出错是难免的,反正我都不会证明,智人见智,别被我误导了。

    §1图论点、边集和二分图的相关概念和性质

    点覆盖、最小点覆盖

    点覆盖集即一个点集,使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。。极小点覆盖(minimal vertex covering):本身为点覆盖,其真子集都不是。最小点覆盖(minimum vertex covering):点最少的点覆盖。点覆盖数(vertex covering number):最小点覆盖的点数。

    边覆盖、极小边覆盖

         边覆盖集即一个边集,使得所有点都与集合里的边邻接。或者说是“边” 覆盖了所有“点”。极小边覆盖(minimal edge covering):本身是边覆盖,其真子集都不是。最小边覆盖(minimum edge covering):边最少的边覆盖。边覆盖数(edge covering number):最小边覆盖的边数。

    独立集、极大独立集

    独立集即一个点集,集合中任两个结点不相邻,则称V为独立集。或者说是导出的子图是零图(没有边)的点集。极大独立集(maximal independent set):本身为独立集,再加入任何点都不是。最大独立集(maximum independent set):点最多的独立集。独立数(independent number):最大独立集的点。

    团即一个点集,集合中任两个结点相邻。或者说是导出的子图是完全图的点集。极大团(maximal clique):本身为团,再加入任何点都不是。最大团(maximum clique):点最多的团。团数(clique number):最大团的点数。

    边独立集、极大边独立集

    边独立集即一个边集,满足边集中的任两边不邻接。极大边独立集(maximal edge independent set):本身为边独立集,再加入任何边都不是。最大边独立集(maximum edge independent set):边最多的边独立集。边独立数(edge independent number):最大边独立集的边数。

    边独立集又称匹配(matching),相应的有极大匹配(maximal matching),最大匹配(maximum matching),匹配数(matching number)。

    支配集、极小支配集

    支配集即一个点集,使得所有其他点至少有一个相邻点在集合里。或者说是一部分的“点”支配了所有“点”。极小支配集(minimal dominating set):本身为支配集,其真子集都不是。最小支配集(minimum dominating set):点最少的支配集。支配数(dominating number):最小支配集的点数。

    边支配集、极小边支配集

    边支配集即一个边集,使得所有边至少有一条邻接边在集合里。或者说是一部分的“边”支配了所有“边”。极小边支配集(minimal edge dominating set):本身是边支配集,其真子集都不是。最小边支配集(minimum edge dominating set):边最少的边支配集。边支配数(edge dominating number):最小边支配集的边数。

    最小路径覆盖

    最小路径覆盖(path covering):是“路径” 覆盖“点”,即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点,即每个顶点严格属于一条路径。路径的长度可能为0(单个点)。

    最小路径覆盖数=G的点数-最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多,但是又不能让两条边在同一个顶点相交。拆点:将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息,从X部往Y部引边。所有边的方向都是由X部到Y部。因此,所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数=原图G的顶点数-二分图的最大匹配数便可以得解。

    匹配

    匹配(matching)是一个边集,满足边集中的边两两不邻接。匹配又称边独立集(edge independent set)。

    在匹配中的点称为匹配点(matched vertex)或饱和点;反之,称为未匹配点(unmatched vertex)或未饱和点。

    交错轨(alternating path)是图的一条简单路径,满足任意相邻的两条边,一条在匹配内,一条不在匹配内

    增广轨(augmenting path):是一个始点与终点都为未匹配点的交错轨。

    最大匹配(maximum matching)是具有最多边的匹配。

    匹配数(matching number)是最大匹配的大小。

    完美匹配(perfect matching)是匹配了所有点的匹配。

    完备匹配(complete matching)是匹配了二分图较小集合(二分图X,Y中小的那个)的所有点的匹配。

    增广轨定理:一个匹配是最大匹配当且仅当没有增广轨。

    所有匹配算法都是基于增广轨定理:一个匹配是最大匹配当且仅当没有增广轨。这个定理适用于任意图。

    二分图的性质

    二分图中,点覆盖数是匹配数。
        (1) 二分图的最大匹配数等于最小覆盖数,即求最少的点使得每条边都至少和其中的一个点相关联,很显然直接取最大匹配的一段节点即可。
        (2) 二分图的独立数等于顶点数减去最大匹配数,很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集,这是|V|-2*|M|,同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。
        (3) DAG的最小路径覆盖,将每个点拆点后作最大匹配,结果为n-m,求具体路径的时候顺着匹配边走就可以,匹配边i→j',j→k',k→l'....构成一条有向路径。

         (4)最大匹配数=左边匹配点+右边未匹配点。因为在最大匹配集中的任意一条边,如果他的左边没标记,右边被标记了,那么我们就可找到一条新的增广路,所以每一条边都至少被一个点覆盖。

         (5)最小边覆盖=图中点的个数-最大匹配数=最大独立集。

    二分图的判定

    二分图是这样一个图: 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中,每个顶点集中没有边直接相连接!

     无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。

     判断二分图的常见方法是染色法: 开始对任意一未染色的顶点染色,之后判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色, 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断,bfs和dfs可以搞定!

    易知:任何无回路的的图均是二分图。

    §2 另外一些姿势

    定理1:最大独立集S 与 最小覆盖集T 互补

    对于无向图:

    最小点覆盖+最大独立集=顶点个数

    最大团=补图的最大独立子集

    关系1:给定图G = (V,E)无孤立点,则G的极大点独立集都是G的极小支配集。

    关系2:G的点覆盖数 a与点独立集数 b满足: a + b = n。

    关系3:G的边覆盖数 a与边独立集数 b满足: a + b = n。(边独立集数即匹配数)

    关系3:给定图G = (V,E)无孤立点,|V | = n。M是G的匹配,W是G的边覆盖,则|M|≤|W|,等号成立时M是G的完美匹配而W是G的最小边覆盖。

    对于二部图

    最小点覆盖数 = 最大匹配数

    最小路径覆盖 = 顶点数 – 最大(二分)匹配数 

    最小边覆盖与最小路径覆盖的区别:

    边覆盖集:通俗地讲,所谓边覆盖集,就是G中所有的顶点都是E*中某条边的邻接顶点(边覆盖顶点),一条边只能覆盖2个顶点。

    注意:在无向图中存在用尽量少的边去“覆盖”住所有的顶点,所以边覆盖集有极小与最小的区别。

    极小边覆盖:若边覆盖E*中的任何真子集都不是边覆盖集,则称E*是极小边覆盖集。

    最小边覆盖:边数最小的边覆盖称为最小边覆盖,通俗地讲,就是极小边覆盖中的最小的一个集合。

    最小边覆盖在二分图中的应用:

    最小边覆盖 = 最大独立集 = n - 最大匹配,这个是二分图上的一个性质。

    最小路径覆盖最小边覆盖不同不要求给的图是二分图,而是要求是PXP的有向图,不能有环,然后根据原图构造二分图,构造方法是将点一分为二,如,i分为i1和i2然后如果i和j有边,那么就在i1和j2之间连一条边。由此构成二分图

    然后最小路径覆盖是n-m,n为原图的点的个数,m为新造二分图的最大匹配。

    要使用上面的最小边覆盖的公式的前提是你已经将点集分成了左右两个点集,如果只是一个无向图的话那么就可以按照下面的做法来做:

    无向图G(V,E)边覆盖的求解步骤:

    1.将无向图拆点,即若在无向图中存在节点i,则将节点i拆为i1,i2分别位于二分图的X部和Y部.若存在边ij,则连接二分图的i1j2,i2j1。

    2.原无向图中的节点数为|V|所以在构造的二分图有2*|V|个节点。在二分图中存在公式:

    2*|V| = 2*二分图的最大匹配数 + 二分图中未匹配的点。其中二分图的最大匹配数+二分图中未匹配的点即覆盖了二分图中所有的点,相对于原无向图,相当于覆盖了每个点两次,即原边覆盖的最小 值转化为二分图的最大匹配数+二分图中未匹配的点的最小值。又有公式2*|V| = 2*二分图的最大匹配数 + 二分图中未匹配的点,可得:

    二分图的最大匹配数+二分图中未匹配的点 = 2*|V| - 二分图的最大匹配数,又此结果为覆盖了原图所有顶点两次,所以结果应该除以2.

    所以无向图的最小边覆盖 = |V| - 二分图的最大匹配数/2.


    §3匈牙利算法的模板(至于这个算法原理就不讲了,自己太弱了)

    const int maxm=10000;
    const int maxn=2005;
    struct node{
        int v,next;
    };
    node edge[maxm];
    int head[maxn];
    int cnt;
    int vis[maxn];
    int link[maxn];
    int ans;
    int n,m,k;
    void add(int u,int v){
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
    }
    bool dfs(int u){
        int v;
        for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].v;
                if(!vis[v]){
                    vis[v]=1;
                    if(link[v]==-1||dfs(link[v])){
                        link[v]=u;
                        return true;
                    }
                }
            }
        return false;
    }
    void work(){
        for(int i=0;i<n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i)){
                ans++;
            }
        }
        return;
    }

    §4我个人的理解(完全是个人 的拙见,仅供参考,说错了大神们勿喷)

    我感觉二分图匹配关键是在于建模应用上,知道了如何建立正确的模型才是重点,下一步进行学习的网络流也是如此。

    首先是对匈牙利模板的一点理解,我个人感觉,其实它只用到了左边集合到右边集合的边,而没有用到右边集合到左边集合的边,因为右边集合到左边集合的边是由link标记所替代,我不知道这样理解是不是正确。但从建模的方法上来说,这个理解应该是可行的。就是说如果你一开始知道一个大的集合是可以被分成左右两个集合的,那么你加边的时候只会加a-》b的边,而不用加b-》a的边,操作上是这样的。但是如果你并不清楚这个集合里那些点是左集合的点,哪些是有集合的点,那么你就要将这些点拆点,然后对于例如1-2的关系,你就要在左边连一条1-》2'的边,还要连一条2-》1’的边,然后最大匹配数就要除以2,具体的建图方法见poj3020,我的理解都是从这个题目上得到的,然后二分图是可以用网络流做的,这个就不多说了。

    §5几种常见建模(大白上的几种与做题遇见的几种)

    1.uva 11419 SAM I AM 类似的有poj3041

    题意是给你一个nxm的棋盘,然后棋盘上有一些目标,你可以竖着打一列或者横着打一行,问你最少需要多少子弹才能把所有目标打完。

    建模方法:将行与列当成左集合与右集合,目标就相当于连接左右集合的边,就是说目标坐标是(x,y)那么它把x行与y列连起来。然后求最小点覆盖就行了。

    2.poj3020  Antenna Placement 类似的还有poj2446
    这个题是最小边覆盖,千万别看网上的博客说是最小路径覆盖就信了,我就是因为想不通为啥是最小路径覆盖才研究了一天,也是我整理这个文章的初衷。

    题意我懒得打了,自己去看原题吧。

    思路有两种,

    一是直接建成二分图,这个需要特别的技巧,即按奇偶建图。

    因为是一个边覆盖两个点,那么这两个点的坐标和(x1+y1)和(x2+y2)必然一个奇数一个偶数,然后分别给图中的奇数偶数点依次从1开始标号,相邻的按其标号建图,建出来的就是二分图,且利用最小边覆盖 = 最大独立集 = n - 最大匹配做即可。

    第二个就是上面提到的无向图边覆盖的做法,如果没想到第一种建图的方法时,就用笨方法,把点集扩大二倍,弄成一个无向图,而不是已分好左右集合的二分图,具体见上面的方法。

    法一代码:
    #include<iostream>
    #include<cstdio>
    #include<vector>
    using namespace std;
    vector<int>map[400];//按奇偶性建二分图 
    int t,n,m;
    int match[400],fy[400],ln,rn; 
    int map1[41][11];//原始图 
    int dirt[4][2]={0,1,0,-1,1,0,-1,0};
    
    int path(int u)
    {
     for(int i=0,j;i<map[u].size();i++)
     {
      j=map[u][i];
      if(!fy[j])
      {
       fy[j]=1;
       if(match[j]==-1||path(match[j]))
       {
        match[j]=u;
        return 1;
       }
      }
     }
     return 0;
    }
    
    int main()
    {
     int i,j,x,y,ans;
     char tmp;
     scanf("%d",&t);
     while(t--)
     {
      scanf("%d%d",&n,&m);
      ln=rn=0;
      for(i=1;i<=n;i++)
      {
       getchar();
       for(j=1;j<=m;j++)
       {
        scanf("%c",&tmp);
        if(tmp=='*')
        {
         if((i+j)&1)//奇点 
          map1[i][j]=++ln;
         else//偶点 
          map1[i][j]=++rn;
        }
        else
         map1[i][j]=0;
       }
      }
      for(i=1;i<=ln;i++)
       map[i].clear();
      for(i=1;i<=rn;i++)
       match[i]=-1;
       
      //建二分图 
      for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
       {
        if(!map1[i][j]||!((i+j)&1))
         continue;
        for(int k=0;k<4;k++)
        {
         x=i+dirt[k][0];
         y=j+dirt[k][1];
         if(x<=0||x>n||y<=0||y>m||!map1[x][y])
          continue;
         map[map1[i][j]].push_back(map1[x][y]);
        }
       }
       
      //求最大匹配 
      ans=0;
      for(i=1;i<=ln;i++)
      {
       for(j=1;j<=rn;j++)
        fy[j]=0;
       if(path(i))
         ans++;
      }
      printf("%d\n",ln+rn-ans);
     }
     return 0;
    }
    法二代码:
    #include<iostream>
    using namespace std;
    
    int ipmap[41][11];   //标记存在城市'*'的位置,并依次记录城市的编号
    int ip;     //城市编号(最终是城市数量)
    int V1,V2;  //二分图的两个顶点集
    int M;      //最大二分匹配
    
    bool city[401][401];   //标记两个城市之间是否能连通
                          //通过“拆点”操作,把每一个城市拆分为2个,分别属于所构造的二分图的两个点集
    bool vist[401];
    int link[401];
    
    int dire_r[4]={-1,1,0,0};
    int dire_c[4]={0,0,-1,1};   //分别对应四个方位 上 下 左 右
    
    
    /*Hungary Algorithm*/
    
    bool dfs(int x)
    {
     for(int y=1;y<=V2;y++)
      if(city[x][y] && !vist[y])
      {
       vist[y]=true;
       if(link[y]==0 || dfs(link[y]))
       {
        link[y]=x;
        return true;
       }
      }
     return false;
    }
    
    void search(void)
    {
     for(int x=1;x<=V1;x++)
     {
      memset(vist,false,sizeof(vist));
      if(dfs(x))
       M++;
     }
     return;
    }
    
    int main(void)
    {
     int test,h,w;
     cin>>test;
     while(test--)
     {
      /*Initial*/
    
      memset(ipmap,0,sizeof(ipmap));
      memset(city,false,sizeof(city));
      memset(link,0,sizeof(link));
      ip=0;
      M=0;
    
      /*Read in the maps*/
    
      cin>>h>>w;
    
      int i,j;
      char temp;
      for(i=1;i<=h;i++)
       for(j=1;j<=w;j++)
       {
        cin>>temp;
        if(temp=='*')
         ipmap[i][j]=++ip;
       }
    
      /*Structure the Bipartite Graphs*/
    
      for(i=1;i<=h;i++)
       for(j=1;j<=w;j++)
        if(ipmap[i][j])
         for(int k=0;k<4;k++)
         {
          int x=i+dire_r[k];
          int y=j+dire_c[k];
          if(ipmap[x][y])
           city[ ipmap[i][j] ][ ipmap[x][y] ]=true;      //"拆点"操作是"顺便"被完成的
         }                                                    //二分图构造完毕后,之后的问题就和POJ3041一样处理了
    
      V1=V2=ip;
    
      /*增广轨搜索*/
    
      search();
    
      /*Output*/
    
      cout<<ip-M/2<<endl;   //无向二分图:最小路径覆盖数 = "拆点"前原图的顶点数 - 最大匹配数/2
     }
     return 0;
    }

    3.LA 3126 出租车 最小路径覆盖

    题意自己去看。这个题中的时间是一个序,也就是说,如果每个客人是一个节点,如果同一个出租车在接完客人u以后来的及接客人v,连u->v,这个图是DAG,且它的最小路径覆盖就是答案。

    #include <stdio.h>  
    #include <string.h>  
    #include <algorithm>
    #define abs(X) ((X) > 0 ? (X) : -(X))
    #define REP(I, X) for(int I = 0; I < X; ++I)
    #define clear(A, X, SIZE) memset(A, X, sizeof(A[0]) * (SIZE + 1))  
    using namespace std;  
    const int maxN = 2000;  
    const int maxE = 1000000;  
    struct Edge{  
            int v, n;  
    }edge[maxE];  
    struct Node{
            int s, e, x1, y1, x2, y2;
    }a[maxN];
    int adj[maxN], cntE, vis[maxN], link[maxN];  
    int n;
    void addedge(int u, int v){  
            edge[cntE].v = v; edge[cntE].n = adj[u]; adj[u] = cntE++;  
    }  
    int find(int u){  
            for(int i = adj[u]; ~i; i = edge[i].n) if(!vis[edge[i].v]){  
                    int v = edge[i].v;  
                    vis[v] = 1;  
                    if(link[v] == -1 || find(link[v])){  
                            link[v] = u;  
                            return 1;
                    }  
            }  
            return 0;  
    }  
    int match(){  
            int ans = 0;  
            clear(link, -1, n);  
            REP(i, n){  
                    clear(vis, 0, n);  
                    ans += find(i);  
            }  
            return ans;  
    }  
    void work(){  
            int h, m;  
            scanf("%d", &n);
            clear(adj, -1, n);  
            cntE = 0;  
            REP(i, n){  
                    scanf("%d:%d%d%d%d%d", &h, &m, &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
                    a[i].s = h * 60 + m;
                    a[i].e = a[i].s + abs(a[i].x1 - a[i].x2) + abs(a[i].y1 - a[i].y2);
            }
            REP(i, n) REP(j, n){ 
                    if(a[i].e + abs(a[i].x2 - a[j].x1) + abs(a[i].y2 - a[j].y1) < a[j].s) addedge(i, j);
            }
            printf("%d\n", n - match());  
    }  
    int main(){ 
            int t; 
            for(scanf("%d", &t); t; --t) work();
            return 0;  
    }  

    4,HDU 2768 猫狗大战 类似的有LA3415

    题意:说每个小孩子都会喜欢一个猫(或狗),讨厌一个狗(猫),管理员会移除一些猫或狗,然后如果留下的动物是这个小孩喜欢的,那么他就高兴,问最多的高兴孩子的个数。

    同样有两种做法。

    一:把喜欢猫的人当成左集合,喜欢狗的人当成右集合,如果喜欢猫的人的这只猫正好是喜欢狗的人讨厌的猫就连条边,说明这俩人是不能同时出现,是矛盾的,然后两个集合内部是不会矛盾的,没有问题,这样建图就是一个二分图,直接按公式做就可以了。

    队友的代码:
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int n,m,k;
    int w[550][550];
    int link[550],used[550];
    int dfs(int u)
    {
        int v;
        for(v=1;v<=k;v++)
        {
            if(w[u][v]&&!used[v])
            {
                used[v]=1;
                if(link[v]==-1||dfs(link[v]))
                {
                    link[v]=u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        int i,j,u,v,ans;
        int c[550];
        char a[550][2][5];
        while(~scanf("%d%d%d",&n,&m,&k))
        {
            for(i=1;i<=k;i++)
            {
                scanf("%s",&a[i][0]);
                scanf("%s",&a[i][1]);
                if(a[i][0][0]=='C') c[i]=0;
                else c[i]=1;
            }
            memset(w,0,sizeof(w));
            for(i=1;i<=k;i++)
                for(j=i+1;j<=k;j++)
                    if(!strcmp(a[i][0],a[j][1])||!strcmp(a[i][1],a[j][0]))
                        w[i][j]=w[j][i]=1;
            memset(link,-1,sizeof(link));
            for(u=1,ans=k;u<=k;u++)
            {
                memset(used,0,sizeof(used));
                if(c[u]&&dfs(u)) ans--;
            }
            printf("%d\n",ans);
        }
        return 0;
    }
    第二个是,不分左右集合,矛盾的两个人之间就连边,求没有连边的观众的数目,就是最大独立集了,但是这个是无向图的,不是分好左右集合的二分图,所以按照最小边覆盖的那种方法做就行了:最小边覆盖 = 最大独立集 = n - 最大匹配。


    展开全文
  • 最小点覆盖: 点覆盖的概念定义: 对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。 最小点覆盖:就是点覆盖中点的个数最少的集合S。 最小边覆盖: 边覆盖的概念定义: 边覆盖是图...

    最小点覆盖:

    点覆盖的概念定义
    对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。

    最小点覆盖:就是点覆盖中点的个数最少的集合S。

    最小边覆盖:

    边覆盖的概念定义:
    边覆盖是图的一个边子集,使该图上每一节点都与这个边子集中的一条边关联,只有含孤立点的图没有边覆盖,边覆盖也称为边覆盖集,图G的最小边覆盖就是指边数最少的覆盖,图G的最小边覆盖的边数称为G的边覆盖数。

    最大匹配:

    匹配:在图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点。

    最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。

    最大独立集:

    最大独立集:在N个点的图G中选出m个点,使这m个点两两之间没有边的点中,m的最大值。

    最小路径覆盖:

    定义:在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。

    (1)二分图的最大匹配

    匈牙利算法(可以用最大流做,但一般匈牙利要快不少)。


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

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


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

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


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

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


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

    我们把原图中的点V拆成两个点Vx和Vy,对于原图中的边A−>B,我们在新图中连Ax−>By。

    那么最少不相交路径覆盖=原图的点数-新图的最大匹配

     

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

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

    例题:POJ - 2594 Treasure Exploration

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

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

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

     

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

    KM算法。(可以用最小费用最大流做)

    展开全文
  • 最小支配集(minimal dominating set):对于图G=(V,E)来说,设V'是图G的一个支配集,则对于图中的任意一个顶点u,要么属于集合V',要么与V'中的顶点相连。...最小点覆盖(minimum point coverage)...
  • 最小点覆盖:指从所有顶点中取尽量少的点组成一个集合,使得集合中所有的边都与取出来的点有边相连。顶点个数最小的覆盖集被称为最小点覆盖。 最大独立集:指从所有顶点中取尽量多的点组成一个集合,使得这些点之间...
  • 图论——二分图——最小点覆盖

    千次阅读 2019-06-20 22:32:38
    最小点集覆盖 == 最大匹配 ①最小点集覆盖<=最大匹配, 假设最小点集覆盖为n, 那么一定能构造出一个为n的匹配, 显然这个匹配<= 最大匹配 ②最小点集覆盖 >= 最大匹配。 假设最大匹配为n,所以肯定有n...
  • 二分图:把分成两个集合X,Y,使得图的边的两个端点总是分别落在X和Y上,不会有X中的连向X中的,不会有Y中的连向Y中的 匹配:实质上是二分图中的一个边集,边集中出现的不会重合,比如有a-b了,就不会...
  • 最小点覆盖问题详解

    千次阅读 2015-06-20 14:36:24
    那么一如既往,还是个人觉得学习某一个知识之前先粗俗的了解其是个什么东东,然后再去了解概念比较好...那么下面结合题目来了解: 首先最最重要的是理解题意,有k个任务,每个任务task_i可以用机器A的x_i模式做,...
  • 最小路劲覆盖 一个不含圈的有向图G 中,G的一个路径覆盖是一个其结点不相交的路径集合P,图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束,且长度也为任意值,包括0。 在有向无环图中 ...
  • nyoj237 游戏高手的烦恼(最小点覆盖)

    千次阅读 2016-04-09 20:05:35
    有一位传说级游戏高手,在闲暇时间里玩起了一个游戏,游戏中,一个n*n的方块形区域里有许多敌人,玩家可以使用炸弹炸掉某一行或者某一列的所有敌人。他是种玩什么游戏都想玩得很优秀的人,所以,他决定,
  • ①最小路径覆盖: 给定有向图G=(V,E)。设P 是G 的一个简单路(顶点不相交)的集合。如果V 中每个顶点恰好在P 的一条路上,则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶点开始,长度也是任意的,特别地,...
  • node 1:最小路径覆盖 在一个PXP的有向图中,路径覆盖就是在图中找一些...(如果把这些路径中的每条路径从它的起始走到它的终点,那么恰好可以经过图中的每个顶点一次且仅一次);如果不考虑图中存在回路,那么
  • 解题报告 题意: 给你一个矩阵,矩阵里面是气球,气球有1-50种颜色,问你在k次之内能不能把那种存在的颜色消掉(每种颜色...求最小点覆盖。用最少的点覆盖最多的边。 每次枚举颜色看是否操作次数超过k次。 英语。。。。
  • 二分图:把分成两个集合X,Y,使得图的边的两个端点总是分别落在X和Y上,不会有X中的连向X中的,不会有Y中的连向Y中的 匹配:实质上是二分图中的一个边集,边集中出现的不会重合,比如有a-b了,就不会有a...
  • 二分图:把分成两个集合X,Y,使得图的边的两个端点总是分别落在X和Y上,不会有X中的连向X中的,不会有Y中的连向Y中的 匹配:实质上是二分图中的一个边集,边集中出现的不会重合,比如有a-b了,就不会有a...
  • 最小支配集:对于图G = (V, E) 来说,最小支配集指的是从 V 中取尽量少的组成一个集合, 使得 V 中剩余的都与取出来的有边相连.也就是说,设 V' 是图的一个支配集,则对于图中的任意一个顶点 u ,要么属于集合 V', ...
  • 大家好,我是Hi和Ho的伙伴Nettle,从这个星期开始由我来完成我们的Weekly。 新年回家,又到了一年一度大龄剩男剩女的相亲时间。Nettle去姑姑家玩的时候看到了一张姑姑写的相亲情况表,上面都是姑姑介绍相亲...
  • 只需要让他们覆盖最大的匹配的M条边,则其他边一定被覆盖(如果有边e不被覆盖,把e加入后得到一个更大的匹配)②M个是必需的,仅考虑形成最大匹配的M条边,由于两两无公共,因此至少需要M个才能把它们覆盖;...
  • 2、最小点覆盖:在图中用尽量少的点去覆盖所有的边(规则:当一个点被覆盖后,在图中与其相邻的边将被覆盖); 3、最大独立集:在图中选择尽量多的点(规则:保证被选则的点在图中没有边相连); 对于任意图上述三...
  • 基础概念: 点的概念 a....b....最大独立集:点独立集中元素个数最大的独立集,那么此独立集元素个数k就是这个图的最大...最小点覆盖集:无向图G中点数最少的点覆盖集 d.最大点独立集:无向图G中,点数最多的点独立
  • 写这篇博客有两个原因,一是由于网上对这些结论的解释和证明太模糊,有些甚至是错的(有的人没分清楚最小路径覆盖和最小边覆盖,用错误的...首先我们来证明选最大匹配数个能否把所有的边都覆盖。 设V为我们选点...
  • 最小路径覆盖

    千次阅读 多人点赞 2018-08-24 10:37:48
    定义:通俗点将,就是在一个有向图中,找出最少的路径,使得这些路径经过了所有的。 最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。 最小不相交路径覆盖:每一条路径经过的顶点各不相同。如图,其...
  • 最小圆覆盖算法

    万次阅读 多人点赞 2016-08-23 16:05:39
         ①首先现将所有随机排列     ②按顺序把一个一个的加入(一步一步的求前i个的最小覆盖圆),每加入一个就进入③     ③如果发现当前i号在当前的最小圆的外面,那么说明i一定在前i个...
  • 1.最小路径点覆盖 DAG中选出最小数量的不相交路径(无公共点),将所有点覆盖。 求法:将DAG中的点拆成出点和入点,构成一个二分图。 则原图的最小路径点覆盖转化到新图中: 1.无公共点->每个点最多只有一个出度...
  • Air Raid + Treasure Exploration 最小边覆盖: 最小路径覆盖: 有向无环图->二分图 传递闭包
  • poj 3020题目大意 一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。问至少放置多少个基站才能使得所有的城市... 定理1:最大匹配数 = 最小点覆盖数(这是

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 591,135
精华内容 236,454
关键字:

最小点覆盖