题目大意：
n*n的网格中有k个小行星，每一次消除能消除掉一整行或一整列的小行星
求摧毁所有的小行星最少需要多少次消除
将位于 i 行 j 列的行星看做连接 i行点 与 j列点 的边
这样找到最小顶点覆盖（即所有边的某一端点包含在选出的点中）
相当于找到最大匹配
#include <bits/stdc++.h> using namespace std; const int N=1005; const int K=10005; int n, k, m[N]; bool vis[N]; struct NODE { int to,nt; }e[K<<1]; int head[N], tot; void addE(int u,int v) { e[tot].to=v; e[tot].nt=head[u]; head[u]=tot++; } /**二分图最大匹配*/ bool dfs(int u) { vis[u]=1; for(int i=head[u];i;i=e[i].nt) { int v=e[i].to, d=m[v]; if(!d || !vis[d]&&dfs(d)) { // v还没匹配 或者 本轮匹配中还没搜过且找到其他匹配 m[u]=v, m[v]=u; return 1; } } return 0; } int match() { int res=0; memset(m,0,sizeof(m)); for(int i=1;i<=n;i++) if(!m[i]) { // 还没匹配 memset(vis,0,sizeof(vis)); if(dfs(i)) res++; // 搜索是否存在合理的匹配 } return res; // 最大匹配个数 } /***/ int main() { while(~scanf("%d%d",&n,&k)) { tot=1; memset(head,0,sizeof(head)); for(int i=0;i<k;i++) { int r,c; scanf("%d%d",&r,&c); addE(r,c+n); //行编号为1~n 列编号为n+1~n+n } // 只建单向边 是因为只从一端找匹配 反向边没意义 printf("%d\n",match()); } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/10121365.html
相关资源：JAVA上百实例源码以及开源项目