题目链接: poj 3041
题目大意: 给出NxN的矩阵,有M个点是障碍
每次只能删除一行或者一列,最少删除多少次才能清除障碍
解题思路: 行作为X集合,列作为Y集合,障碍就是两集合间的连线
问题转化为如何使得选取最少的点,覆盖掉所有的直线
由König定理可得
最小点集覆盖==最大匹配数,匈牙利求最大匹配
代码:
#include <stdio.h> #include <string.h> #include <string.h> #define MAX 510 int n,edge[MAX][MAX],cx[MAX],cy[MAX],visit[MAX],sum; int DFS(int u) //匈牙利 { int i; for(i=1;i<=n;i++) { if(!visit[i]&&edge[u][i]) { visit[i]=1; if(!cy[i]||DFS(cy[i])) //** { cx[u]=i; cy[i]=u; return 1; } } } return 0; } int main() { int i,j,k,a,b; while(scanf("%d%d",&n,&k)!=EOF) { memset(edge,0,sizeof(edge)); memset(cx,0,sizeof(cx)); memset(cy,0,sizeof(cy)); for(i=1;i<=k;i++) { scanf("%d%d",&a,&b); edge[a][b]=1; //单向边 } for(i=1,sum=0;i<=n;i++) { if(!cx[i]) //x匹配y { memset(visit,0,sizeof(visit)); sum+=DFS(i); //增广轨 } } printf("%d\n",sum); } return 0; }