蒟蒻问个简单题,蒙了,玄2关,请大佬看看!!!
  • 板块灌水区
  • 楼主OIDragon
  • 当前回复10
  • 已保存回复10
  • 发布时间2024/1/5 20:41
  • 上次更新2024/1/5 20:56:51
查看原帖
蒟蒻问个简单题,蒙了,玄2关,请大佬看看!!!
775893
OIDragon楼主2024/1/5 20:41

蒟蒻在一个紫题做到76分时,思考了4h没有进展,看了题解(对,没错,我承认了)

看的是一个大佬的,思路明白了,但是代码。。。有个地方不懂,贴出来请教一下各位大佬↓

#include <iostream>

const int maxN = 150;
const int maxM = 6000;

int n, m;
int u, v;

namespace graph {
    struct Vertex {
        int vis;
        int head;
        int match;
    } vertex[2 * maxN + 10];

    struct Edge {
        int head;
        int next;
    } edge[maxM + 10];

    int ecnt;

    void addEdge(int tail, int head) {
        ecnt++;
        edge[ecnt].head = head;
        edge[ecnt].next = vertex[tail].head;
        vertex[tail].head = ecnt;
        return;
    }

    bool DFS(int u, int t) {
        for (int e = vertex[u].head; e; e = edge[e].next) {
            int v = edge[e].head;
            if (vertex[v].vis == t) continue;
            vertex[v].vis = t;
            if (vertex[v].match == 0 || DFS(vertex[v].match, t)) {
                vertex[v].match = u;
                vertex[u].match = v;
                return true;
            }
        }
        return false;
    }
}

void print(int u) {
    while (u != - n) {
        std::cout << u << ' ';
        u = graph::vertex[u].match - n;//这里的graph::是什么作用?
    }
    std::cout << '\n';
    return;
}

int main() {
    int matched = 0;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) std::cin >> u >> v, graph::addEdge(u, n + v);
    for (int i = 1; i <= n; i++) if (graph::DFS(i, i)) matched++;
    for (int i = 1; i <= n; i++) if (graph::vertex[i + n].match == 0) print(i);//这里的也是,啥作用?
    std::cout << n - matched << '\n';
    return 0;
}

蒟蒻没接触过这种写法,就是一个结构体里包含一堆结构体和函数,这是啥意思?

还有,如果不用graphgraph这个结构体,直接用函数,要怎么改代码?

拜求大佬解答!!!回复有用信息的就关注!

2024/1/5 20:41
加载中...