这题应该算是一道比较简单的二分图问题,可是我压根还是没想到二分图,一看解题报告说用二分图,再一琢磨就明白了。。。。就是求二分图的最大匹配和关键匹配
code:
#include <cstdio> #include <cstring> using namespace std; int n,m,k; int link[101]; bool graph[101][101],vis[101]; struct pos { int x,y; }p[101*101]; bool find(int x) { int y; for(y=1;y<=m;y++) { if(graph[x][y] && !vis[y]) { vis[y]=true; if(link[y]==0 || find(link[y])) { link[y]=x; return true; } } } return false; } int solve() { int x,ans=0; memset(link,0,sizeof(link)); for(x=1;x<=n;x++) { memset(vis,false,sizeof(vis)); if(find(x)) { ans++; } } return ans; } int main() { int i,ans,cnt,cas=0; while(~scanf("%d%d%d",&n,&m,&k)) { cnt=0; memset(graph,false,sizeof(graph)); for(i=1;i<=k;i++) { scanf("%d%d",&p[i].x,&p[i].y); graph[p[i].x][p[i].y]=true; } ans=solve(); for(i=1;i<=k;i++) { graph[p[i].x][p[i].y]=false; if(solve()<ans) { cnt++; } graph[p[i].x][p[i].y]=true; } printf("Board %d have %d important blanks for %d chessmen.\n",++cas,cnt,ans); } return 0; }