题目链接: hdu 1281
题目大意: 给出NxM的棋盘,其中有K个点不能放“车”
定义:若某个点不能放"车",则棋盘中放"车"的最大数目减少该点就为重要点
求重要点的个数和棋盘中放"车"的最大数目
解题思路: 求出放"车"的最大数目,行作为X集合,列作为Y集合
空白的地方是X集合和Y集合之间的连线,求最大匹配数
然后枚举每条边,把这条边删除掉,若放"车"的最大数目减少,该点就是重要点
时间复杂度为O(k*n^3),k是集合间的边数,n是集合中的顶点数
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 105 struct snode{ int a,b; }listb[MAX*MAX]; int n,m,edge[MAX][MAX],cx[MAX],cy[MAX],visit[MAX]; int DFS(int u) //DFS增广轨 { int i; for(i=1;i<=m;i++) { if(edge[u][i]&&!visit[i]) { visit[i]=1; if(!cy[i]||DFS(cy[i])) { cy[i]=u; cx[u]=i; return 1; } } } return 0; } int main() { int i,j,k,a,b,sum,temp,kk,tt=0; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { tt++; sum=0; memset(cx,0,sizeof(cx)); memset(cy,0,sizeof(cy)); memset(edge,0,sizeof(edge)); memset(visit,0,sizeof(visit)); for(i=1;i<=k;i++) { scanf("%d%d",&a,&b); listb[i].a=a,listb[i].b=b; edge[a][b]=1; //单向边 } for(i=1;i<=n;i++) { if(!cx[i]) { memset(visit,0,sizeof(visit)); sum+=DFS(i); } } for(i=1,kk=0;i<=k;i++) //枚举每条边,删掉之后最大匹配数是否改变 { memset(cx,0,sizeof(cx)); memset(cy,0,sizeof(cy)); edge[listb[i].a][listb[i].b]=0; for(j=1,temp=0;j<=n;j++) { if(!cx[j]) { memset(visit,0,sizeof(visit)); //初始化 temp+=DFS(j); //每次增加1 } } edge[listb[i].a][listb[i].b]=1; if(temp<sum) kk++; } printf("Board %d have %d important blanks for %d chessmen.\n",tt,kk,sum); } return 0; }