HDU 1507 Uncle Tom's Inherited Land*（二分匹配，输出任意一组解）

HDU 1507 Uncle Tom's Inherited Land*（二分匹配，输出任意一组解）

要输出任意一组解。

一开始时两边都是n*m-k个点做的，答案输出一半，但是错掉了，匹配数没有问题，就是输出解会出错。

后来按照奇偶分成两部分就可以了

#include#include#include#include#includeusing namespace std;const int MAXN=510;int uN,vN;int g[MAXN][MAXN];int linker[MAXN];bool used[MAXN];bool dfs(int u){ for(int v=0;v 0 && a[i-1][j]!=-1) g[u][a[i-1][j]]=1; if(i < n-1 && a[i+1][j]!=-1) g[u][a[i+1][j]]=1; if(j > 0 && a[i][j-1]!=-1) g[u][a[i][j-1]]=1; if(j < m-1 && a[i][j+1]!=-1) g[u][a[i][j+1]]=1; } int ans = hungary(); printf("%d\n",ans); for(int i = 0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。