|
第一次写这玩意,还真有点麻烦,出了点问题。然后看了一下别人的代码, 发现双向边,要分成两个单向边来插入。长见识了。 而且费用的值有正有负,最好用SPFA来找最短路径。 思路: 建立一个超级源点,跟点1连起来,容量为2。 建立一个超级汇点,跟点N连起来,容量为2。 其他的边容量均为1。
#include <stdio.h> #include <stdlib.h> #include <string.h>
#define MAX_COST (1 << 30) #define MAX_E (20032 * 4) #define MAX_V 2048 #define MAX_CAP 2 #define dbp printf
struct edge_node { int idx, flow, cap, cost; struct edge_node *next; };
struct graph_node { struct edge_node edges[MAX_E], *map[MAX_V], *path_edge[MAX_V]; int edges_cnt, vertexs_cnt, path_idx[MAX_V]; int min_dis[MAX_V]; };
inline int min(int a, int b) { return a < b ? a : b; }
inline void graph_init(struct graph_node *g, int vertexs_cnt) { g->vertexs_cnt = vertexs_cnt; g->edges_cnt = 0; memset(g->map, 0, vertexs_cnt * sizeof(g->map[0])); }
inline void graph_dump(struct graph_node *g) { struct edge_node *e; int i;
for (i = 0; i < g->vertexs_cnt; i++) { dbp("#%d: ", i); for (e = g->map[i]; e; e = e->next) dbp("%dc%d ", e->idx, e->cost); dbp("\n"); } }
inline void graph_addedge(struct graph_node *g, int from, int to, int cost, int cap = 0 ) { struct edge_node *e;
if (g->edges_cnt >= _countof(g->edges)) { printf("too many edges\n"); return ; }
e = &g->edges[g->edges_cnt++]; e->idx = to; e->cost = cost; e->cap = cap; e->next = g->map[from]; g->map[from] = e; }
inline int __conn_default(struct edge_node *e) { return 1; }
inline void graph_spfa(struct graph_node *g, int idx, int (*conn)(struct edge_node *) = __conn_default ) { static int queue[MAX_V], vis[MAX_V], tm, head, tail; int i, val; struct edge_node *e;
for (i = 0; i < g->vertexs_cnt; i++) g->min_dis[i] = MAX_COST; g->min_dis[idx] = 0; head = tail = 0; tm++; queue[tail++] = idx;
while (head != tail) { idx = queue[head++]; vis[idx] = 0; for (e = g->map[idx]; e; e = e->next) { if (!conn(e)) continue; val = g->min_dis[idx] + e->cost; if (val >= g->min_dis[e->idx]) continue; g->path_idx[e->idx] = idx; g->path_edge[e->idx] = e; g->min_dis[e->idx] = val; if (vis[e->idx] == tm) continue; queue[tail++] = e->idx; vis[e->idx] = tm; } } }
inline int __conn_mfmc(struct edge_node *e) { return e->cap - e->flow > 0; }
inline void graph_mfmc(struct graph_node *g, int s, int t, int *flow, int *cost) { int i, j, min_c; struct edge_node *e;
for (i = 0; i < g->edges_cnt; i++) g->edges[i].flow = 0;
*flow = 0; *cost = 0; while (1) { graph_spfa(g, s, __conn_mfmc); if (g->min_dis[t] == MAX_COST) break ; min_c = MAX_CAP; for (i = t; i != s; i = g->path_idx[i]) { e = g->path_edge[i]; min_c = min(min_c, e->cap - e->flow); } for (i = t; i != s; i = g->path_idx[i]) { j = g->path_edge[i] - g->edges; *cost += g->edges[j].cost * min_c; g->edges[j].flow += min_c; g->edges[j ^ 1].flow -= min_c; } *flow += min_c; } }
int main() { int N, M, from, to, cost, flow; static struct graph_node g;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &M); graph_init(&g, N + 2); while (M--) { scanf("%d%d%d", &from, &to, &cost); graph_addedge(&g, from, to, cost, 1); graph_addedge(&g, to, from, -cost, 0); graph_addedge(&g, to, from, cost, 1); graph_addedge(&g, from, to, -cost, 0); } graph_addedge(&g, 0, 1, 0, 2); graph_addedge(&g, 1, 0, 0, 0); graph_addedge(&g, N, N + 1, 0, 2); graph_addedge(&g, N + 1, N, 0, 0); graph_mfmc(&g, 0, N + 1, &flow, &cost); printf("%d\n", cost);
return 0; }
|