|
|
第一次寫這玩意，還真有點麻煩，出了點問題。然后看了一下別人的代碼， 發(fā)現(xiàn)雙向邊，要分成兩個單向邊來插入。長見識了。 而且費用的值有正有負，最好用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;
}
|