HDU 1498 坐标轴二分匹配

给定n k

下面n*n的矩阵，每个格子用一个数字表示气球一种颜色

每次选择一行或一列爆破 同行(列) 的同色气球

排序输出： 选择k次仍不能全部爆完的气球颜色

思路：

对于一种颜色

把该颜色所有的点坐标

(i,j) 建边

匹配出一个i,j 表示 x轴坐标i被匹配了 当所有x轴坐标被匹配时，就是所有气球被爆破了

这样得到的匹配数就是 这种颜色需要爆破的次数

若次数>k 则输出这种颜色

#include <iostream>#include <cstdio>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <cstdlib>#include <vector>#include <math.h>#define N 105using namespace std;int lef[N*N], pn;//lef[v]表示Y集的点v 当前连接的点  bool T[N*N];     //T[u] 表示x集 u 是否已连接y集vector<int>G[N]; //匹配边  G[X集].push_back(Y集)  注意G 初始化bool match(int x){ // x和Y集 匹配 返回x点是否匹配成功for(int i=0; i<G[x].size(); i++){int v = G[x][i];if(!T[v]){T[v] = true;if(lef[v] == -1 || match( lef[v] )){lef[v] = x;return true;}}}return false;}int solve(){int aaa = 0;memset(lef, -1, sizeof(lef));for(int i = 1; i<= pn; i++)//X集匹配，X集点标号从 1-pn 匹配边是G[左点].size()   {memset(T, 0, sizeof(T));if( match( i ) ) aaa++;}return aaa;}int k,n;int map[N][N][N];int se[N];void Clear(){for(int i=0;i<=n;i++)G[i].clear();}void init(){int i,j,t;memset(se, 0, sizeof(se));memset(map,0,sizeof(map));for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&t);map[t][i][j] = 1;se[t] = 1;}}}int ans[N];int main(){int i,j,z;while(~scanf("%d %d", &n, &k), n!=0 && k!=0){init();int top = 0;pn = n;for(i=1;i<=50;i++){if(se[i]){Clear();for(j = 1; j <= n; j++)for(z = 1; z <= n; z++)if(map[i][j][z])G[j].push_back(z);if( solve() > k)ans[top++] = i;}}if(!top)printf("-1\n");else {for(i=0;i<top-1;i++)printf("%d ",ans[i]);printf("%d\n",ans[i]);}}return 0;}/*1 112 01 11 22 11 22 25 41 2 3 4 52 3 4 5 13 4 5 1 24 5 1 2 35 1 2 3 43 350 50 5050 50 5050 50 50ans:-1121 2 3 4 5-1*/