hdu1845 Jimmy’s Assignment --- 完整匹配-白红宇

hdu1845 Jimmy’s Assignment --- 完整匹配

阅读量：6991 次

发布时间：2019-06-27

本文共 1131 字，大约阅读时间需要 3 分钟。

意甲冠军：

它需要一个特殊的图，以找到最大匹配。该图的特征是：无向图，度的每个节点3。这是一个双边连接组件（the graph is 2-edge-connected (that is, at least 2 edges need to be removed in order to make the graph disconnected) 这一点是这样理解的把。。）

思路：

一般想法就直接建图求最大匹配，点的范围是5000，不优化可能超时，以下代码是890ms过的。

还有一种思路：

完备匹配的条件：

1. G是K（K>0）次正则二分图

2.G是无桥的三次正则图

3.G在去掉随意一个顶点子集S后，其子图中含顶点数为奇数的连通分支数不大于|S|

具有以上三个特征的图一定有完备匹配。且当中第三点是完备匹配的充要条件。

据此可得。题目中所给的图一定是完备匹配。答案是n/2。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            const int maxn=5010;using namespace std;int main(){ int n,a,b,t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<3*n/2;i++) scanf("%d%d",&a,&b); printf("%d\n",n/2); } return 0;}

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            const int maxn=5010;using namespace std;int mx[maxn],my[maxn],n;bool vis[maxn];vector
             
               e[maxn];int path(int i){ int j,sz=e[i].size(); for(j=0;j

你可能感兴趣的文章