这个题卡了好久，发现还有什么二分图匹配这个东西。。然后简单搞了一下

二分图:

二分图又称二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可以分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A, j in B), 则称图G是二分图。e.g.
匹配：
给定一个二分图，在G的一个子图G’中，如果G’的边集中的任意两条边都不依附于同一个顶点，则称G’的边集为G的一个匹配
最大匹配：
在所有的匹配中，边数最多的那个匹配就是二分图的最大匹配了
顶点覆盖：
在顶点集合中，选取一部分顶点，这些顶点能够把所有的边都覆盖了。这些点就是顶点覆盖集
最小顶点覆盖：
在所有的顶点覆盖集中，顶点数最小的那个叫最小顶点集合。
独立集：
在所有的顶点中选取一些顶点，这些顶点两两之间没有连线，这些点就叫独立集
最大独立集：
在左右的独立集中，顶点数最多的那个集合
路径覆盖：
在图中找一些路径，这些路径覆盖图中所有的顶点，每个顶点都只与一条路径相关联。
最小路径覆盖：
在所有的路径覆盖中，路径个数最小的就是最小路径覆盖了。
熟悉了这些概念之后，还有一个二分图最大匹配的K?nig定理，这个定理的内容是：最大匹配 = 最小顶点覆盖。此处不证明其正确性。有了这个定理之后还可以得出一些二分图特有的公式：
最大独立集=最小路径覆盖数 = 顶点个数 ? 最小顶点覆盖（最大匹配）
这个公式，我们可以利用最大匹配来找到最大的独立集。而最大独立集和最小路径覆盖有个千丝万缕的关系。

对于二分图的最大匹配，常用的求解方法是hungarian算法和最大流算法。

此题就是求最小路径覆盖

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define N 20005 stack
       
        sta; vector
        
         mp[N]; vector
         
          mp2[N]; int match[N]; int dfn[N]; int low[N]; int InStack[N]; int indexx,number; int n, m; int id[N]; int vis[N]; void tarjan(int u) { InStack[u] = 1; low[u] = dfn[u] = ++ indexx; sta.push(u); for (int i = 0; i < mp[u].size(); ++ i) { int t = mp[u][i]; if (dfn[t] == 0) { tarjan(t); low[u] = min(low[u], low[t]); } else if (InStack[t] == 1) { low[u] = min(low[u], dfn[t]); } } if (low[u] == dfn[u]) { ++ number; while (!sta.empty()) { int v = sta.top(); sta.pop(); id[v]=number; InStack[v] = 0; if (v == u) break; } } } int path(int s)//求匹配度 { for(int i=0; i

hdu 3861强连通分量+最小图匹配

这个题卡了好久，发现还有什么二分图匹配这个东西。。然后简单搞了一下