50 years, 50 colors
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1720 Accepted Submission(s): 949
color balloons".
There will be a n*n matrix board on the ground, and each grid will have a color balloon in it.And the color of the ballon will be in the range of [1, 50].After the referee shouts "go!",you can begin to crash the balloons.Every time you can only choose one kind
of balloon to crash, we define that the two balloons with the same color belong to the same kind.What's more, each time you can only choose a single row or column of balloon, and crash the balloons that with the color you had chosen. Of course, a lot of students
are waiting to play this game, so we just give every student k times to crash the balloons.
Here comes the problem: which kind of balloon is impossible to be all crashed by a student in k times.
n*n, where Aij denote the color of the ballon in the i row, j column.Input ends with n = k = 0.
1 1 1 2 1 1 1 1 2 2 1 1 2 2 2 5 4 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 3 3 50 50 50 50 50 50 50 50 50 0 0
-1 1 2 1 2 3 4 5 -1
/* n*n的矩阵放置不同的颜色(不同的数字代表不同的颜色), 你有k次选择,每一次只能选择某一行或某一列,可以消除该行(列)的所有颜色, 问有哪几种颜色,无论怎样经过k次选择后依然无法完全抹去。 将横纵坐标为x,y集合 每个颜色的坐标对应一条边, 求最小点(横或纵,即为需要射击的次数)覆盖对应边的个数, 每次可以消去该点的匹配的边 哪种颜色的气球不能在K次中被消灭( 每次只能消灭一行或者一列 ) 对于某种颜色的匹配,如果他的最大匹配大于k,则该颜色在k次里无论如何都无法抹去的。 最小点覆盖=最大匹配 */ #include<iostream> #include<stdio.h> #include<algorithm> using namespace std; #define N 105 int n,k; int map[N][N],vis[N],match[N],use[N],ans[N]; bool cmp(int a,int b) { return a<b; } int dfs(int u,int color) { int i; for(i=1;i<=n;i++) { if(map[u][i]==color&&!vis[i])//对应的某一列是否存在该color { vis[i]=1; if(match[i]==-1||dfs(match[i],color)) { match[i]=u; return 1; } } } return 0; } int hungary(int color) { int a=0,i; memset(match,-1,sizeof(match)); for(i=1;i<=n;i++)//行 { memset(vis,0,sizeof(vis)); if(dfs(i,color)) a++; } return a; } int main() { int i,j,m,sum; //freopen("test.txt","r",stdin); while(scanf("%d%d",&n,&k)) { if(n==0&&k==0) break; memset(map,0,sizeof(map)); memset(use,0,sizeof(use)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&map[i][j]); m=0;// for(i=1;i<=n;i++) for(j=1;j<=n;j++) { sum=0; if(!use[map[i][j]])//该颜色没有出现过 寻找该颜色的需要多少次消除 { use[map[i][j]]=1; sum=hungary(map[i][j]); } if(sum>k) ans[m++]=map[i][j];// 统计大于K次的颜色 } if(m==0) printf("-1\n"); else { sort(ans,ans+m,cmp); for(i=0;i<m;i++) { if(i) printf(" "); printf("%d",ans[i]); } printf("\n"); } } return 0; }