Bài tập C Chu trình và đường đi EULER

tengiday:

Mình làm câu 4 cho bạn nhé (Euler cycle: chu trình qua các cạnh, mỗi cạnh 1 lần). Đề quá ngắn gọn, mình không có nhiều thời gian, nên mình sẽ assume rằng:
- Input lúc nào cũng có chu trình Euler cả (đỉnh bậc chẵn).
Code đơn giản nhất đây:

Mã:

#include <vector>
#include <stack>

#define MAX_DIGITS 64

std::vector<int> EulerCycle(std::vector<std::vector<int>> &a) {
    std::vector<int> result;
    if (a.empty()) return result;
    std::stack<int> s;
    s.push(0);
    while (!s.empty()) {
        int x = s.top();
        for (int i = 0; i < (int)a.size(); ++i)
            if (a[x][i] > 0) {
                --a[x][i];
                --a[i][x];
                s.push(i);
                break;
            }
        if (x == s.top()) {
            s.pop();
            result.push_back(x);
        }
    }
    return result;
}

void EulerProblem(char * inputF, char * outputF) {
    FILE * f = fopen(inputF, "r");
    if (f == 0) {
        printf("%s not found.\n", inputF);
        return;
    }
    char s[MAX_DIGITS];
    fgets(s, MAX_DIGITS, f);
    int n(0), m(0), x(-1), y(-1);
    sscanf(s, "%d %d", &n, &m);
    std::vector<std::vector<int>> a(n, std::vector<int>(n, 0));
    while (fgets(s, MAX_DIGITS, f) != 0) {
        sscanf(s, "%d %d", &x, &y);
        a[y][x] = ++a[x][y];
    }
    fclose(f);
    
    std::vector<int> result = EulerCycle(a);

    f = fopen(outputF, "w");
    if (result.empty()) {
        fprintf(f, "-1\n");
        fclose(f);
        return;
    }
    for (int i = (int)result.size() - 1; i > 0; --i)
        fprintf(f, "%d -> ", result[i]);
    fprintf(f, "%d\n", result[0]);
    fclose(f);
}

Độ phức tạp của thuật toán O(|E|), linear theo số cạnh, nếu optimize được quá trình tìm cạnh chưa đi (vòng 'for' bên trong có thể đơn giản).

Bạn đang học phần này àh? Mấy câu trên có vẻ lý thuyết quá; hoàn toàn có trong sách mà.
Đường đi tối thiểu bao phủ đồ thị là gì mình không rõ. Tối thiểu là đg` đi ngắn nhất? Bao phủ là bao phủ đỉnh hay cạnh?

Nhấn để mở rộng...

tengiday:

Mình đã làm câu 4 rồi; riêng câu 5 mình cần biết rõ về giả thuyết. Ý nghĩa "bao phủ tối thiểu", đồ thị vô hướng hay có hướng. Kiến thức của mình toàn bằng tiếng Anh cả nên mình ko rõ thuật ngữ chuyên môn tiếng Việt. Nếu bạn nói đến path cover với đồ thị vô hướng thì ko có thuật toán đa thức nhé. Nếu là đồ thị có hướng thì đưa bài toán này về bài stable matching, cặp ghép, thì sẽ có giải thuật tốt.

Nhấn để mở rộng...

hienn366:

vậy cho xin 2 dạng
có hướng và vô hướng đi bạn

cảm ơn bạn đã trợ giúp!

Nhấn để mở rộng...

tengiday:

Bạn giải thích (định nghĩa) rõ "bao phủ tối thiểu" và "đg` đi" ở trong bài là thế nào trc đã. Ví dụ đơn giản như hình chữ Y, thì ko cách gì đi qua mỗi đỉnh mà đi liên tục và mỗi đỉnh đi đúng 1 lần đc (chỉ có thể đi lại, hoặc xuất phát từ đỉnh khác để tạo thành 2 đg` đi). Như vậy cái đg` đi ở đây đc định nghĩa như thế nào? Ngoài ra, đồ thị có trọng sô hay không có, trọng số không âm hay như thế nào? Bạn quyết định luôn vô hướng hay có hướng nhé vì mình ko có thời gian code 2 bài.
Nhiều bài graph cho tới nay cũng ko có thuật toán tốt.

Nhấn để mở rộng...