蓝桥杯官网 试题 PREV-113 历届真题 估计人数【第十届】【决赛】【研究生组】【C++】【Java】【Python】三种解法

#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;
}

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;
    }
    
    
    
}

# 弗洛伊德
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)