NYOJ 239：

ural 1109 :

NYOJ 月老的难题，是裸的最大匹配，很烦的是邻接阵超时。改用邻接表。

#include 
      
       using namespace std;#define maxn 1005vector 
       
         G[maxn];bool use[maxn];int match[maxn];int m,n,k;bool dfs(int u){    for(int i=0;i
       
      

然后是ural,最小路径覆盖。

题意：

A国家有M个代表，B国有N个代表，其中有K对代表可以进行谈判（一个是A国的，一个是B国的），并且每一个代表至少被包含在其中一对中（也就是说，每个 人可以至少找到另外一个人谈判），每一对谈判需要一对电话联系（一对电话联系数目算1），现在使每个人都能进行电话联系的最少联系数目。

就是求最少对数。每个点都要有边相连，这样的边最少是多少——最小路径覆盖。

首先求一下最大匹配(都是一对一)，可能还有没有匹配的人，加上这些人，如案例： 最大匹配2，还有左边2号没有匹配。加上这个人。

得公式：

最小路径覆盖 = n+ m - 2 * ans + ans;

#include 
      
       using namespace std;#define maxn 1005vector 
       
         G[maxn];bool use[maxn];int match[maxn];int m,n,k;bool dfs(int u){    for(int i=0;i