蓝桥杯官网 试题 PREV-113 历届真题 估计人数【第十届】【决赛】【研究生组】【

为帮助大家能在6月18日的比赛中有一个更好的成绩，我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。

今年的最大目标就是能为【一亿技术人】创造更高的价值。

---

资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500;

int mat[25][25];
int link[205][205];
int moves[2][2] = {{1,0},{0,1}};
int match[MAXN];
bool vis[MAXN];
int n,m,num,total = 0;;

void floyd(){
for(int k = 1;k<=total;k++){
for(int i = 1;i<=total;i++){
for(int j = 1;j<=total;j++){
if(!link[i][j] && link[i][k] && link[k][j])
link[i][j] = 1;
}
}
}
}

bool found(int x){
for(int v = 1;v<=total;v++){
if(!vis[v] && link[x][v]){
vis[v] = true;
if(match[v] == 0||found(match[v])){
match[v] = x;
return true;
}
}
}
return false;
}

int main(){
scanf("%d %d",&n,&m);
memset(mat,0,sizeof(mat));
memset(match,0,sizeof(match));
memset(link,0,sizeof(link));
string str;
for(int i = 0;i<n;i++){
cin>>str;
for(int j = 0;j<m;j++){
num = str[j] - '0';
if(num)mat[i][j] = ++total;
else mat[i][j] = 0;
}
}

for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(!mat[i][j])continue;
for(int k = 0;k<2;k++){
int dx = i + moves[k][0];
int dy = j + moves[k][1];
if(dx < 0 || dy <0 || dx >= n || dy >=m)continue;
if(mat[dx][dy])link[mat[i][j]][mat[dx][dy]] = 1;
}
}
}
floyd();
int res = 0;
for(int i = 1;i<=total;i++){

memset(vis,0,sizeof(vis));
if(found(i))res++;
}
printf("%d\n",total - res);
return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main{
static boolean[][] conect;
static boolean[] visited;
static int[] friend;
static int sum = 1;

public static void main(String[] args) throws IOException, InterruptedException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sl = br.readLine().split(" +");
int N = Integer.parseInt(sl[0]);
int M = Integer.parseInt(sl[1]);
int[][] list = new int[N][M];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
if(Integer.parseInt(s.charAt(j)+"") == 1)
list[i][j] = sum++;
}
}
friend = new int[sum];
conect = new boolean[sum][sum];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(list[i][j]==0)
continue;
if(i!=N-1 && list[i+1][j] > 0) {
conect[list[i][j]][list[i+1][j]] = true;
}
if(j!=M-1 && list[i][j+1] > 0) {
conect[list[i][j]][list[i][j+1]] = true;
}
}
}

for (int i = 1; i < sum; i++) {
for (int j = 1; j < sum; j++) {
if(!conect[i][j])
continue;
for (int j2 = 0; j2 < sum; j2++) {
if(conect[j][j2] && i!=j2)
conect[i][j2] = true;
}
}
}

int TT = 0;
for (int i = 1; i < sum; i++) {
visited = new boolean[sum];
if(xyl(i))
TT++;
}

System.out.println(sum-1-TT);

}


static boolean xyl(int i) {
for (int j = 1; j < sum; j++) {
if(conect[i][j] && !visited[j]) {
visited[j] = true;
if(friend[j]==0 || xyl(friend[j])) {
friend[j] = i;
return true;
}
}
}
return false;
}



}

Python

# 弗洛伊德
def floyd(n):
for k in range(1, n + 1): # 当前考虑的中间节点
for i in range(1, n + 1): # 遍历图中的每一个节点
for j in range(1, n + 1):# 考虑该节点的所有可能的邻接节点
if new_graph[i][k] * new_graph[k][j] == 1:
new_graph[i][j] = 1
# 匈牙利
def dfs(node, node_cot):
for k in range(1, node_cot+1):
if new_graph[node][k] == 1:
if visited[k] == 0:
visited[k] = 1
if connected[k] == -1 or dfs(connected[k] ,node_cot):
connected[k] = node
return True
return False

dx = [0, 1]
dy = [1, 0]
N, M = list(map(int, input().split()))
graph = [[0 for i in range(M)] for j in range(N)]


node_cot = 0
for i in range(N):
strr = input()
for j in range(M):
e = int(strr[j])
if e == 1:
node_cot += 1
graph[i][j] = [e, node_cot]
else:
graph[i][j] = [e, -1]

new_graph = [[0 for i in range(node_cot + 1)] for j in range(node_cot + 1)]
for i in range(N):
for j in range(M):
if graph[i][j][0] == 1:
node_idx = graph[i][j][1]
for x in range(2):
new_i = i + dx[x]
new_j = j + dy[x]
if 0 <= new_i < N and 0 <= new_j < M and graph[new_i][new_j][0] == 1:
new_graph[node_idx][graph[new_i][new_j][1]] = 1

floyd(node_cot)

cot = 0

visited = [0 for i in range(node_cot + 1)]
connected = [-1 for i in range(node_cot + 1)]
for i in range(1, node_cot + 1):
visited = [0 for i in range(node_cot + 1)]
if dfs(i, node_cot):
cot += 1
print(node_cot - cot) 【文章原创作者：美国服务器 https://www.68idc.cn 欢迎留下您的宝贵建议】