Untitled

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_NODES 10000
#define MAX_LINKS 10000

// 節點結構
typedef struct Node {
    int id;
    int quantumMemories;
} Node;

// 鏈路結構
typedef struct Link {
    int id1, id2;
    double distance;
    double fidelity;
    int entangledLinks;
} Link;

// 參數
double alpha, beta, swapProb;

// 節點和鏈路的陣列以及計數器
Node nodes[MAX_NODES];
int nodeCount = 0;

Link links[MAX_LINKS];
int linkCount = 0;

// 計算基礎保真度
double calculate_fidelity(double distance) {
    return 0.5 + 0.5 * exp(-beta * distance);
}

// 糾纏鏈路純化操作
double purify_fidelity(double F1, double F2) {
    return (F1 * F2) / (F1 * F2 + (1 - F1) * (1 - F2));
}

double probability(double fidelity) {
    return exp(-alpha * fidelity);
}

// 新增節點到陣列
void add_node(int id, int quantumMemories) {
    if (nodeCount >= MAX_NODES) {
        fprintf(stderr, "Error: Exceeded maximum number of nodes.\n");
        exit(1);
    }
    nodes[nodeCount].id = id;
    nodes[nodeCount].quantumMemories = quantumMemories;
    nodeCount++;
}

// 根據ID查找節點
Node* find_node(int id) {
    for (int i = 0; i < nodeCount; i++) {
        if (nodes[i].id == id) {
            return &nodes[i];
        }
    }
    return NULL;
}

// 新增鏈路到陣列
void add_link(int id1, int id2, double distance) {
    if (linkCount >= MAX_LINKS) {
        fprintf(stderr, "Error: Exceeded maximum number of links.\n");
        exit(1);
    }
    links[linkCount].id1 = id1;
    links[linkCount].id2 = id2;
    links[linkCount].distance = distance;
    links[linkCount].entangledLinks = 1;
    Node *node1 = find_node(id1);
    Node *node2 = find_node(id2);
    if (node1 == NULL || node2 == NULL) {
        fprintf(stderr, "Error: Node not found.\n");
        exit(1);
    }
    node1->quantumMemories--;
    node2->quantumMemories--;
    links[linkCount].fidelity = calculate_fidelity(distance);
    linkCount++;
}

// 初始化節點和鏈路
void initialize_nodes_and_links() {
    int totalNodes;
    scanf("%d %lf %lf %lf", &totalNodes, &alpha, &beta, &swapProb);

    if (totalNodes > MAX_NODES) {
        fprintf(stderr, "Error: Total nodes exceed maximum allowed.\n");
        exit(1);
    }

    for (int i = 0; i < totalNodes; i++) {
        int id, quantumMemories;
        scanf("%d %d", &id, &quantumMemories);
        add_node(id, quantumMemories);
    }

    for (int i = 0; i < totalNodes - 1; i++) {
        int id1;
        double distance;
        scanf("%d %lf", &id1, &distance);
        add_link(id1, id1 + 1, distance);
    }
}

// 貪婪算法：選擇提升保真度最多的鏈路來進行更新
void greedy_algorithm() {
    while (1) {
        Link *bestLink = NULL;
        double maxFidelityGain = 0.0;

        // 遍歷所有鏈路，計算每個鏈路增加一條糾纏鏈路後的保真度增益
        for (int i = 0; i < linkCount; i++) {
            Link *link = &links[i];
            Node *node1 = find_node(link->id1);
            Node *node2 = find_node(link->id2);

            if (node1->quantumMemories > 0 && node2->quantumMemories > 0) {
                // 計算純化後的保真度
                double newFidelity = purify_fidelity(link->fidelity, calculate_fidelity(link->distance));
                double fidelityGain = newFidelity - link->fidelity;

                // 更新最大保真度增益和鏈路
                if (fidelityGain > maxFidelityGain) {
                    maxFidelityGain = fidelityGain;
                    bestLink = link;
                }
            }
        }

        // 如果沒有可用的鏈路進行更新，則退出循環
        if (bestLink == NULL) {
            break;
        }

        // 對選中的鏈路進行更新
        Node *node1 = find_node(bestLink->id1);
        Node *node2 = find_node(bestLink->id2);
        node1->quantumMemories--;
        node2->quantumMemories--;
        bestLink->fidelity = purify_fidelity(bestLink->fidelity, calculate_fidelity(bestLink->distance));
        bestLink->entangledLinks++;
    }
}

// 打印結果
void print_result() {
    // 順著打印鏈路
    for (int i = 0; i < linkCount; i++) {
        printf("%d %d %d\n", links[i].id1, links[i].id2, links[i].entangledLinks);
    }
}

int main() {
    // 初始化節點和鏈路
    initialize_nodes_and_links();

    // 執行貪婪算法
    greedy_algorithm();

    // 打印結果
    print_result();

    return 0;
}