机试第11章

并查集

const int MAXN = 1000;
int fa[MAXN], h[MAXN];

void init(int n)
{
    for (int i = 0; i < n; ++i)
        fa[i] = i, h[i] = 0;
}

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

void uni(int x, int y)
{
    x = find(x), y = find(y);
    if (x != y)
    {
        if (h[x] < h[y])
            fa[x] = y;
        else if (h[x] > h[y])
            fa[y] = x;
        else
        {
            h[x]++;
            fa[y] = x;
        }
    }
}

判断无向图是否连通

bool isConnected()
{
    int cnt = 0; // 连通分量个数
    for (int i = 1; i < n; ++i)
        if (find(i) == i)
            cnt++;
    return cnt == 1;
}

判断有向图是否为树

int degree[MAXN]; // 入度，在union时改变

void init(int n)
{
    for (int i = 0; i < n; ++i)
        degree[i] = 0;
}

bool isTree()
{
    bool flag = true;
    int cnt = 0;
    int root = 0;
    for (int i = 0; i < MAXN; ++i)
    {
        if (fa[i] == i)
            cnt++;
        if (degree[i] == 0)
            root++;
        else if (degree[i] > 1)
        {
            flag = false;
            break;
        }
    }
    if (cnt != 1 || root != 1)
        flag = false;
    if (cnt == 0 || root == 0)
        flag = true;
    return flag;
}

最小生成树Kruskal算法

struct edge
{
    int s, e, w;
    bool operator<(const edge &e) const
    {
        return w < e.w;
    }
};
edge edges[MAXN * MAXN];

int kruskal(int n, int len)
{
    init(n); // 初始化并查集
    sort(edges, edges + len);
    int res = 0;
    for (int i = 0; i < len; ++i)
    {
        edge cur = edges[i];
        if (find(cur.s) != find(cur.e))
        {
            uni(cur.s, cur.e);
            res += cur.w;
        }
    }
    return res;
}

最短路

单源最短路Dijkstra算法

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const int INF = INT_MAX;

struct edge
{
    int to, length;
    edge(int to, int length) : to(to), length(length) {}
};

struct point
{
    int num, dis;
    point(int num, int dis) : num(num), dis(dis) {}
    bool operator<(const point &x) const
    {
        return dis > x.dis;
    }
};

vector<edge> graph[MAXN];
int dis[MAXN];

void dijkstra(int s)
{
    priority_queue<point> q;
    q.push({s, 0});
    while (!q.empty())
    {
        int u = q.top().num;
        q.pop();
        for (int i = 0; i < graph[u].size(); ++i)
        {
            int v = graph[u][i].to, d = graph[u][i].length;
            if (dis[v] > dis[u] + d)
            {
                dis[v] = dis[u] + d;
                q.push({v, dis[v]});
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    memset(graph, 0, sizeof(graph));
    fill(dis, dis + n, INF);
    while (m--)
    {
        int from, to, length;
        cin >> from >> to >> length;
        graph[from].push_back({to, length});
        graph[to].push_back({from, length});
    }

    int s, t;
    cin >> s >> t;
    if (dis[t] == INF)
        dis[t] = -1;
    cout << dis[t] << "\n";
    return 0;
}

多源最短路Floyd算法

#include <bits/stdc++.h>
using namespace std;

const int INF = INT_MAX;

int main()
{
    int n, target;
    cin >> n >> target;
    vector<vector<int>> g(n + 1, vector<int>(n + 1, INF));
    vector<vector<int>> next(n + 1, vector<int>(n + 1));
    for (int i = 0; i < n; ++i)
    {
        g[i][i] = 0;
        next[i][i] = i;
    }
    int src, dst, dis;
    while (cin >> src >> dst >> dis)
    {
        g[src][dst] = dis;
        next[src][dst] = dst;
    }

    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (g[i][k] == INF || g[k][j] == INF)
                    continue;
                else if (g[i][k] + g[k][j] < g[i][j])
                {
                    g[i][j] = g[i][k] + g[k][j];
                    next[i][j] = k;
                }

    int cur = 1;
    cout << cur;
    while(cur!=target)
    {
        cur = next[cur][target];
        cout << " " << cur;
    }
    return 0;
}

拓扑排序

const int MAXN = 500;
vector<int> graph[MAXN];
int inDegree[MAXN];

vector<int> TopologicalSort(int n)
{
    vector<int> res;
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; ++i)
        if (inDegree[i] == 0)
            q.push(i);

    while (!q.empty())
    {
        int u = q.top();
        q.pop();
        res.push_back(u);
        for (int i = 0; i < graph[u].size(); ++i)
        {
            int v = graph[u][i];
            inDegree[v]--;
            if (inDegree[v] == 0)
                q.push(v);
        }
    }
    return res;
}

关键路径

const int MAXN = 1e5;
const int INF = INT_MAX;
vector<int> graph[MAXN];
int inDegree[MAXN];
int earliest[MAXN], latest[MAXN], time[MAXN];

int CriticalPath(int n)
{
    vector<int> topology;
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (inDegree[i] == 0)
            q.push(i);

    int total = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        topology.push_back(u);
        for (int i = 0; i < graph[u].size(); ++i)
        {
            int v = graph[u][i];
            earliest[v] = max(earliest[v], earliest[u] + time[u]);
            inDegree[v]--;
            if (inDegree[v] == 0)
            {
                q.push(v);
                total = max(total, earliest[v] + time[v]);
            }
        }
    }

    for (int i = topology.size() - 1; i >= 0; --i)
    {
        int u = topology[i];
        if (graph[u].size() == 0) // 无后继的节点
            latest[u] = total - time[u];
        else
            latest[u] = INF;
        for (int j = 0; j < graph[u].size(); ++j)
        {
            int v = graph[u][j];
            latest[u] = min(latest[u], latest[v] - time[u]);
        }
    }
    return total;
}