2.12学习总结

今天加强了Kruskal算法，开始学习Dijkstra算法，开始复习bfs/dfs算法

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

int n, m, s, t;
int parent[20005];
typedef struct {
    int u, v, w;
} node;
node load[20005];

int cmp(const void* a, const void* b)
{
     node* nodeA = (node*)a;
     node* nodeB = (node*)b;
    return nodeA->w - nodeB->w;
}

int find(int x)
{
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

void Kru()
{
    int ans = 0;
    for (int i = 1; i <= n; i++) 
    {
        parent[i] = i;
    }
    qsort(load, m, sizeof(node), cmp);
    for (int i = 0; i < m; i++)
    {
        int x = load[i].u;
        int y = load[i].v;
        int w = load[i].w;
        if (find(x) != find(y)) 
        {
            unionSet(x, y);
            ans = w;
        }
        if (find(s) == find(t)) 
            break;
    }
    printf("%d", ans);
}

int main() 
{
    scanf("%d %d %d %d", &n, &m, &s, &t);
    for (int i = 0; i < m; i++)
       scanf("%d %d %d", &load[i].u, &load[i].v, &load[i].w);
    Kru();
    return 0;
}

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

#define MAX_N 1005
#define MAX_M 100005

int n, m;
int f[MAX_N];

typedef struct {
    int x, y, t;
} load;

load loads[MAX_M];

int cmp(const void* a, const void* b) 
{
    load* loadA = (load*)a;
    load* loadB = (load*)b;
    return loadA->t - loadB->t;
}

int find(int x) 
{
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}

void unionSet(int x, int y) 
{
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY)
        f[rootX] = rootY;
}

int isAllConnected()
{
    int root = find(1);
    for (int i = 2; i <= n; i++) 
    {
        if (find(i) != root)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++)
        scanf("%d %d %d", &loads[i].x, &loads[i].y, &loads[i].t);

    qsort(loads, m, sizeof(load), cmp);

    for (int i = 1; i <= n; i++)
        f[i] = i;

    int ans = -1;
    for (int i = 0; i < m; i++) 
    {
        int x = loads[i].x;
        int y = loads[i].y;
        int t = loads[i].t;

        unionSet(x, y);

        if (isAllConnected()) 
        {
            ans = t;
            break;
        }
    }

    printf("%d", ans);

    return 0;
}

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

#define MAXN 10005
#define MAXM 500005
#define INF 0x7fffffff

// 边的结构体
typedef struct Edge {
    int to;
    int next;
    int weight;
} Edge;

Edge edges[MAXM];
int head[MAXN];
int dist[MAXN];
int visited[MAXN];
int edgeCount = 0;

// 添加边
void addEdge(int u, int v, int w) {
    edges[edgeCount].to = v;
    edges[edgeCount].weight = w;
    edges[edgeCount].next = head[u];
    head[u] = edgeCount++;
}

// Dijkstra 算法
void dijkstra(int s, int n) {
    // 初始化距离数组为无穷大
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[s] = 0;

    for (int i = 1; i <= n; i++) {
        int minDist = INF, u = -1;
        // 找到距离源点最近且未访问的点
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }

        if (u == -1) break;
        visited[u] = 1;

        // 更新与 u 相邻的点的距离
        for (int j = head[u]; j != -1; j = edges[j].next) {
            int v = edges[j].to;
            int w = edges[j].weight;
            if (!visited[v] && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
}

int main() {
    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);

    // 初始化 head 数组
    memset(head, -1, sizeof(head));

    // 读取边的信息
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w);
    }

    // 执行 Dijkstra 算法
    dijkstra(s, n);

    // 输出结果
    for (int i = 1; i <= n; i++) {
        if (i > 1) printf(" ");
        printf("%d", dist[i] == INF? 0x7fffffff : dist[i]);
    }
    printf("\n");

    return 0;
}