?

?

根据题目描述，什么是重要点？在求出最大匹配后，进行枚举，依次删边，看最大匹配数会不会发生改变，改变的话，那么该点就是重要点。

?

?

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define init(a) memset(a,0,sizeof(a)) #define PI acos(-1,0) using namespace std; const int maxn = 110; const int maxm = 10100; #define lson left, m, id<<1 #define rson m+1, right, id<<1|1 #define min(a,b) (a>b)?b:a #define max(a,b) (a>b)?a:b int mar[maxn][maxn]; int G[maxn][maxn]; int line[maxn]; bool vis[maxn]; int n,m,k; int DFS(int u) { for(int v = 1;v<=m;v++) { if(G[u][v] && !vis[v]) { vis[v] = 1; if(line[v] == -1 || DFS(line[v])) { line[v] = u; return 1; } } } return 0; } int K_M() { int ans = 0; memset(line,-1,sizeof(line)); for(int i = 1;i<=n;i++) { init(vis); ans += DFS(i); } return ans; } int main() { int x[maxm],y[maxm],C = 0; while(scanf(%d%d%d,&n,&m,&k)!=EOF) { C++; init(G); for(int i = 1;i<=k;i++) { scanf(%d%d,&x[i],&y[i]); G[x[i]][y[i]] = 1; } int ans = K_M(); int num = 0; for(int i = 1;i<=k;i++) { G[x[i]][y[i]] = 0;//删边 if(ans > K_M()) num++; G[x[i]][y[i]] = 1;//恢复 } printf(Board %d have %d important blanks for %d chessmen. ,C,num,ans); } return 0; }
       
      
     
    
   
  

?