acwing::acwing4298类 参考

AcWing 4298. 搭档 更多...

#include <acwing.h>

Public 成员函数
bool	find (int i)
int	main (istream &cin, ostream &cout)

Private 属性
int *	a = nullptr
	男孩魅力值
int *	b = nullptr
	女孩魅力值
bool **	connected = nullptr
	邻接矩阵存图
bool *	found = nullptr
	记录女孩是否已经被找到
int	m = 0
	女孩数量
int *	match = nullptr
	记录当前女孩所对应的男孩
int	n = 0
	男孩数量

详细描述

AcWing 4298. 搭档

在文件 acwing.h 第 1032 行定义.

成员函数说明

find()

bool acwing::acwing4298::find

(

int

i

)

在文件 acwing.cpp 第 3255 行定义.

                               {
        for(int j = 0; j < m; j++) {
            if(connected[i][j] && !found[j]) {
                //可以配对且女孩未被找到
                found[j] = true;
                if(match[j] == -1 || find(match[j])) {
                    //女孩没有配对的对象或女孩配对的对象可以找到其他对象去配对
                    match[j] = i;//设置女孩j和男孩i配对
                    return true;
                }
            }
        }
        return false;
    }

引用了 connected, find(), found, m , 以及 match.

被这些函数引用 find() , 以及 main().

main()

int acwing::acwing4298::main	(	istream &	cin,
		ostream &	cout )

在文件 acwing.cpp 第 3207 行定义.

                                                    {
        cin >> n;
        a = new int[n];
        memset(a, 0, n * sizeof(int));
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cin >> m;
        b     = new int[m];
        found = new bool[m];
        match = new int[m];
        memset(b, 0, m * sizeof(int));
        memset(found, 0, m * sizeof(bool));
        memset(match, -1, m * sizeof(int));
        for(int i = 0; i < m; i++) {
            cin >> b[i];
        }
        connected = new bool *[n];
        for(int i = 0; i < n; i++) {
            connected[i] = new bool[m];
            for(int j = 0; j < m; j++) {
                if(abs(a[i] - b[j]) <= 1) {
                    connected[i][j] = true;
                } else {
                    connected[i][j] = false;
                }
            }
        }
 
        int ans = 0;
        for(int i = 0; i < n; i++) {
            memset(found, 0, m * sizeof(bool));
            if(find(i)) {
                ans++;
            }
        }
        cout << ans;
        for(int i = 0; i < n; i++) {
            delete[] connected[i];
        }
        delete[] connected;
        delete[] a;
        delete[] b;
        delete[] found;
        delete[] match;
        return 0;
    }

引用了 a, b, connected, find(), found, m, match , 以及 n.

类成员变量说明

a

int* acwing::acwing4298::a = nullptr

private

男孩魅力值

在文件 acwing.h 第 1035 行定义.

被这些函数引用 main().

b

int* acwing::acwing4298::b = nullptr

private

女孩魅力值

在文件 acwing.h 第 1036 行定义.

被这些函数引用 main().

connected

bool** acwing::acwing4298::connected = nullptr

private

邻接矩阵存图

在文件 acwing.h 第 1038 行定义.

被这些函数引用 find() , 以及 main().

found

bool* acwing::acwing4298::found = nullptr

private

记录女孩是否已经被找到

在文件 acwing.h 第 1037 行定义.

被这些函数引用 find() , 以及 main().

m

int acwing::acwing4298::m = 0

private

女孩数量

在文件 acwing.h 第 1034 行定义.

被这些函数引用 find() , 以及 main().

match

int* acwing::acwing4298::match = nullptr

private

记录当前女孩所对应的男孩

在文件 acwing.h 第 1039 行定义.

被这些函数引用 find() , 以及 main().

n

int acwing::acwing4298::n = 0

private

男孩数量

在文件 acwing.h 第 1033 行定义.

被这些函数引用 main().

---

该类的文档由以下文件生成:

• acwing.h
• acwing.cpp