本题就是先推断能否够组成二分图，然后用匈牙利算法求出最大匹配。
究竟怎样学习一种新算法呢？
我也不知道什么方法是最佳的了，由于看书本和大牛们写的匈牙利算法具体分析，看了几乎相同两个小时没看懂，最后自己直接看代码，竟然不到半个小时看懂了。然后就能够直接拿来解题啦。
比方topcoder上有这个算法的非常具体的分析。真没看懂。
代码竟然比分析更清晰了？我也不好下结论。
可是我认为基本的思想还是有作用的。
说说我对这个算法的理解吧：
1 假设二分图分为两个集合 U， V，那么从一个集合U出发
2 U的一个点u连线到V的一个点v，假设v点没有别的点连接，那么就算连接成功了
3 假设v点有别的点u2连接了。那么就u2就须要让u连接，然后u2递归寻找别的路径点去连接。假设寻找成功找到v2。那么u2就连接v2；
4 假设u2没有找到别的点连接，那么u2就不让u了，所以u就不能连接v了。
5 那么u就继续寻找别的点连接，反复上述过程，直到u没找到别的点连接。那么u就是连接失败。继续下一个点查找。
就是一个递归查找的过程。
这位大牛的分析。我也是没看懂：https://www.byvoid.com/blog/hungary
可是能够參考他的图。然后依照我上面说的方法连接以下的图。保证你懂了：
本题C++程序：
bool isBipartite_2(vector<vector<bool> > & stus, int src)
{
vector<int> colors(stus.size(), -1);
colors[src] = 0;
queue<int> qu;
qu.push(src);
while (qu.size())
{
int u = qu.front();
qu.pop();
for (int v = 0; v < (int)stus.size(); v++)
{
if (stus[u][v] && colors[v] == -1)
{
colors[v] = 1 - colors[u];
qu.push(v);
}
else if (stus[u][v] && colors[v] == colors[u]) return false;
}
}
return true;
}
bool hunDfs_2(vector<vector<bool> > &stus, vector<bool> &used,
vector<int> &linker, int src)
{
for (int d = 0; d < (int)stus.size(); d++)
{
if (stus[src][d] && !used[d])
{
used[d] = true;
if (linker[d] == -1 ||
hunDfs_2(stus, used, linker, linker[d]))
{
linker[d] = src;
return true;
}
}
}
return false;
}
int hungary_2(vector<vector<bool> > &stus)
{
int res = 0;
vector<int> linker(stus.size(), -1);
for (int i = 0; i < (int)stus.size(); i++)
{
vector<bool> used(stus.size(), false);
if (hunDfs_2(stus, used, linker, i)) res++;
}
return res;
}
int main()
{
int n, m, u, v;
while (scanf("%d %d", &n, &m) != EOF)
{
vector<vector<bool> > stus(n, vector<bool>(n, 0));
while (m--)
{
scanf("%d %d", &u, &v);
stus[u-1][v-1] = stus[v-1][u-1] = true;//记得：这是个无向图,否则错
}
if (isBipartite_2(stus, 0))
{
printf("%d
", hungary_2(stus)>>1);
}
else puts("No");
}
return 0;
}