题意：n*n的格子，每行和每列都是1~n的每个数出现一次。给出前k行，补全剩下的n-k行。1<=n<=100,0<k<=n.
题解：二分匹配裸题。
1.假如第i行有100种填写方法，那么每一种均可，不会出现第p种填写方案使后面行无法填写而第q种填写方案使后面行可以填写的情况。
2.逐行匹配即可。
#include<bits/stdc++.h> #define N 105 using namespace std ; int n , m ; int a[N][N] ; int match[N] ; bool vis[N] ; bool used[N][N] ; bool dfs(int x) { int i , j ; for(i = 1 ; i <= n ; i ++) { if(!used[x][i] && !vis[i]) { vis[i] = 1 ; if(match[i] == -1 || dfs(match[i])) { match[i] = x ; return 1 ; } } } return 0 ; } bool judge_row() { int i , j ; bool vis1[N] ; for(i = 1 ; i <= n ; i ++) { memset(vis1 , 0 , sizeof(vis1)) ; for(j = 1 ; j <= n ; j ++) vis1[a[i][j]] = 1 ; for(j = 1 ; j <= n ; j ++) if(!vis1[j]) return 0 ; } return 1 ; } bool judge_col() { int i , j ; bool vis1[N] ; for(j = 1 ; j <= n ; j ++) { memset(vis1 , 0 , sizeof(vis1)) ; for(i = 1 ; i <= n ; i ++) vis1[a[i][j]] = 1 ; for(i = 1 ; i <= n ; i ++) if(!vis1[i]) return 0 ; } return 1 ; } int main() { int i , j ; int ans ; bool flag = 1 ; memset(used , 0 , sizeof(used)) ; scanf("%d%d" , &n , &m) ; for(i = 1 ; i <= m ; i ++) for(j = 1 ; j <= n ; j ++) { scanf("%d" , &a[i][j]) ; used[j][a[i][j]] = 1 ; } for(i = m + 1 ; i <= n ; i ++) { ans = 0 ; memset(match , -1 , sizeof(match)) ; for(j = 1 ; j <= n ; j ++) { memset(vis , 0 , sizeof(vis)) ; if(dfs(j)) ans ++ ; } if(ans < n) { flag = 0 ; break ; } for(j = 1 ; j <= n ; j ++) a[i][match[j]] = j ; for(j = 1 ; j <= n ; j ++) used[j][a[i][j]] = 1 ; } if(!judge_row() || !judge_col()) flag = 0 ; if(flag == 0) printf("no") ; else { printf("yes\n") ; for(i = 1 ; i <= n - 1 ; i ++) { for(j = 1 ; j <= n - 1 ; j ++) printf("%d " , a[i][j]) ; printf("%d\n" , a[i][n]) ; } for(j = 1 ; j <= n - 1 ; j ++) printf("%d " , a[n][j]) ; printf("%d" , a[n][n]) ; } }
