嗯...

 

题目链接：http://poj.org/problem?id=3041

 

这道题的思想比较奇特：

把x坐标、y坐标分别看成是二分图两边的点，如果（x，y）上有行星，则将（x，y）之间连一条边，而我们要做的就是要找尽量少的点把所有的边覆盖，即为最小点覆盖问题，根据König定理：最小覆盖点数=最大匹配数，所以就可以用匈牙利算法求最大匹配了。

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int match[505], vis[505], g[505][505], n; 8  9 inline int dfs(int u){10     for(int i = 1; i <= n; i++){11         if(g[u][i] && !vis[i]){12             vis[i] = 1;13             if(!match[i] || dfs(match[i])){14                 match[i] = u;15                 return 1;16             }17         }18     }19     return 0;20 }//匈牙利21 22 inline int hungary(){23     int ans = 0;24     for(int i = 1; i <= n; i++){25         memset(vis, 0, sizeof(vis));26         if(dfs(i)) ans++;27     }28     return ans;29 }30 31 int main(){32     int k;33     while(~scanf("%d%d", &n, &k)){34         for(int i = 1; i <= k; i++){35             int r, c;36             scanf("%d%d", &r, &c);37             g[r][c] = 1;38         }39         printf("%d\n", hungary());40     }41     return 0;42 }