首页 > 代码库 > poj 3041
poj 3041
一开始没思路 看了别人的结题报告恍然大悟
题意:给定n*n的矩阵 和一些点 现在想要把这些点全部清除掉 每次只能清除每一行或每一列的所有的点 问至少需要清除多少次
思路:最小点覆盖 把每一 每一列 分别看做两个点集 矩阵中的点看做所在行点与列点的边 则问题就变成了求最小点覆盖
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<iostream> #include<cstring> using namespace std; int map[555][555]; int fa[555]; int s[555]; int k,n; bool dfs( int u) { int i; for (i=1;i<=n;i++) if (map[u][i]&&!s[i]) { s[i]=1; if (!fa[i]||dfs(fa[i])) { fa[i]=u; return true ; } } return false ; } int main() { int x,y,i; int sum; while ( scanf ( "%d%d" ,&n,&k)!=EOF) { sum=0; memset (fa,0, sizeof (fa)); memset (map,0, sizeof (map)); while (k--) { scanf ( "%d%d" ,&x,&y); map[x][y]=1; // map[y][x]=1; } for (i=1;i<=n;i++) { memset (s,0, sizeof (s)); if (dfs(i)) sum++; } printf ( "%d\n" ,sum); } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。