一般预流推进算法带高度函数的C语言代码

以下是一般预流推进算法带高度函数的C语言代码：

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

#define MAX_N 1000

/* 定义边结构体 */
typedef struct Edge {
    int to; // 边的终点
    int cap; // 边的流量
    int rev; // 反向边的编号
} Edge;

/* 定义图结构体 */
typedef struct Graph {
    Edge *edges[MAX_N]; // 存储每个节点的边
    int num_edges[MAX_N]; // 存储每个节点的边的数量
    int height[MAX_N]; // 存储每个节点的高度
    int excess[MAX_N]; // 存储每个节点的超额流
    int num_nodes; // 节点数量
    int num_edges_total; // 边数量
} Graph;

/* 初始化图 */
void init_graph(Graph *g, int n) {
    int i;
    for (i = 0; i < n; i++) {
        g->num_edges[i] = 0;
        g->height[i] = 0;
        g->excess[i] = 0;
    }
    g->num_nodes = n;
    g->num_edges_total = 0;
}

/* 添加边 */
void add_edge(Graph *g, int from, int to, int cap) {
    Edge *e1 = (Edge *) malloc(sizeof(Edge));
    Edge *e2 = (Edge *) malloc(sizeof(Edge));
    e1->to = to;
    e1->cap = cap;
    e1->rev = g->num_edges[to];
    e2->to = from;
    e2->cap = 0;
    e2->rev = g->num_edges[from];
    g->edges[from][g->num_edges[from]++] = e1;
    g->edges[to][g->num_edges[to]++] = e2;
    g->num_edges_total++;
}

/* 计算节点的高度 */
void calc_height(Graph *g, int s) {
    int i;
    for (i = 0; i < g->num_nodes; i++) {
        g->height[i] = -1;
    }
    g->height[s] = g->num_nodes;
    int queue[g->num_nodes];
    int front = 0;
    int rear = 0;
    queue[rear++] = s;
    while (front < rear) {
        int u = queue[front++];
        int i;
        for (i = 0; i < g->num_edges[u]; i++) {
            Edge *e = g->edges[u][i];
            if (e->cap > 0 && g->height[e->to] == -1) {
                g->height[e->to] = g->height[u] - 1;
                queue[rear++] = e->to;
            }
        }
    }
}

/* 计算节点的超额流 */
void calc_excess(Graph *g, int u) {
    int i;
    for (i = 0; i < g->num_edges[u]; i++) {
        Edge *e = g->edges[u][i];
        if (e->cap > 0 && g->height[u] > g->height[e->to]) {
            int f = e->cap < g->excess[u] ? e->cap : g->excess[u];
            g->excess[u] -= f;
            g->excess[e->to] += f;
            e->cap -= f;
            g->edges[e->to][e->rev]->cap += f;
        }
    }
}

/* 计算最大流 */
int max_flow(Graph *g, int s, int t) {
    int i, j;
    for (i = 0; i < g->num_nodes; i++) {
        for (j = 0; j < g->num_edges[i]; j++) {
            g->edges[i][j]->cap = g->edges[i][j]->cap;
        }
    }
    calc_height(g, t);
    g->excess[s] = INT_MAX;
    int i;
    for (i = 0; i < g->num_edges[s]; i++) {
        Edge *e = g->edges[s][i];
        int f = e->cap;
        g->excess[s] -= f;
        g->excess[e->to] += f;
        e->cap -= f;
        g->edges[e->to][e->rev]->cap += f;
    }
    int u;
    while (1) {
        int flag = 1;
        for (u = 0; u < g->num_nodes; u++) {
            if (g->excess[u] > 0) {
                flag = 0;
                calc_excess(g, u);
            }
        }
        if (flag) {
            break;
        }
    }
    return g->excess[t];
}

/* 测试 */
int main() {
    Graph g;
    init_graph(&g, 6);
    add_edge(&g, 0, 1, 16);
    add_edge(&g, 0, 2, 13);
    add_edge(&g, 1, 2, 10);
    add_edge(&g, 1, 3, 12);
    add_edge(&g, 2, 1, 4);
    add_edge(&g, 2, 4, 14);
    add_edge(&g, 3, 2, 9);
    add_edge(&g, 3, 5, 20);
    add_edge(&g, 4, 3, 7);
    add_edge(&g, 4, 5, 4);
    int max_flow = max_flow(&g, 0, 5);
    printf("最大流为：%d\n", max_flow);
    return 0;
}

这段代码可以求解一个有向图的最大流，其中每条边都有一个流量限制。该算法使用了预流推进算法和高度函数的概念，以提高算法的效率。