用C语言写代码解决电路布线问题

以下是一个简单的用C语言解决电路布线问题的示例代码：

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

#define MAX_NODES 100
#define MAX_EDGES 1000

typedef struct {
    int x, y;
} Point;

typedef struct {
    int from, to;
    double weight;
} Edge;

Point nodes[MAX_NODES];
Edge edges[MAX_EDGES];

int cmp(const void *a, const void *b) {
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;
    if (a1->weight < b1->weight) {
        return -1;
    } else if (a1->weight > b1->weight) {
        return 1;
    } else {
        return 0;
    }
}

void kruskal(int n, int m) {
    int i, j, k;
    int parent[MAX_NODES];
    double cost = 0;
    for (i = 0; i < n; i++) {
        parent[i] = i;
    }
    qsort(edges, m, sizeof(Edge), cmp);
    for (i = 0; i < m; i++) {
        int from = edges[i].from;
        int to = edges[i].to;
        double weight = edges[i].weight;
        int root1 = from, root2 = to;
        while (root1 != parent[root1]) {
            root1 = parent[root1];
        }
        while (root2 != parent[root2]) {
            root2 = parent[root2];
        }
        if (root1 != root2) {
            cost += weight;
            parent[root1] = root2;
            printf("(%d,%d) %lf\n", from, to, weight);
        }
    }
    printf("Cost of minimum spanning tree: %lf\n", cost);
}

int main() {
    int n, m, i, j, k;
    printf("Enter the number of nodes: ");
    scanf("%d", &n);
    printf("Enter the coordinates of the nodes:\n");
    for (i = 0; i < n; i++) {
        scanf("%d %d", &nodes[i].x, &nodes[i].y);
    }
    k = 0;
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            double distance = sqrt(pow(nodes[i].x - nodes[j].x, 2) + pow(nodes[i].y - nodes[j].y, 2));
            edges[k].from = i;
            edges[k].to = j;
            edges[k].weight = distance;
            k++;
        }
    }
    m = k;
    printf("Enter the number of edges: ");
    scanf("%d", &m);
    printf("Enter the edges and their weights:\n");
    for (i = 0; i < m; i++) {
        scanf("%d %d %lf", &edges[i].from, &edges[i].to, &edges[i].weight);
    }
    kruskal(n, m);
    return 0;
}

该示例代码使用了Kruskal算法来求解电路布线问题，其思路是将电路看作带权无向图，通过求解最小生成树来得到最优的布线方案。在代码中，我们首先输入节点的坐标，根据节点坐标计算出边的权重，然后使用Kruskal算法求解最小生成树并输出结果。需要注意的是，该示例代码只是一个简单的示例，实际的电路布线问题可能会更加复杂，需要根据具体情况进行调整和修改。