时间限制：0.25s
空间限制：4M
题意：
在n（n<=400）个点的图中，找到并输出两条不想交的最短路。不存在输出“No sulotion”；
Solution：
最小费用最大流
建图与poj 2135 一样,添加S到1的流量为2权为0,n到T的流量为2权为0的边,其它边的流量为1,权为路径长度.
但是这道题麻烦不在要输出最短路，而在仅仅4M的内存上。
由于只有4M，我们最多存上400*400条边.但是图却是一个无向图,朴素的想法是存上400*400*2条边,但是这里内存不够.
所以我们首先要确定记录一条边我们是否使用过,如果使用了使用的是那个方向.
相应的在找到增广路后,把正向反向边的流量改变,把反向边的费用变成负值.
最后按照我们标记过的边dfs,并输出就好了.
总的来说是一道足以加深对最小费用最大流的理解的不错的题!
参考代码:
/* 最小费用最大流算法： 思路： 以费用为权做最短路算法。*/#include#include #include #include #include using namespace std;const int INF = 409, Maxn = 0x3f3f3f3f;struct node { int u, v, t, c, next;} edge[INF * INF];int head[INF], nCnt = 1;int G[INF][INF];void addEdge (int u, int v, int traffic, int cost) { edge[++nCnt].v = v, edge[nCnt].u = u, edge[nCnt].t = traffic, edge[nCnt].c = cost; edge[nCnt].next = head[u], head[u] = nCnt; edge[++nCnt].v = u, edge[nCnt].u = v, edge[nCnt].t = traffic, edge[nCnt].c = cost; edge[nCnt].next = head[v], head[v] = nCnt;}int max_flow, min_cost;int n, m, SS, ST, S, T, min_dis = Maxn;int SPFA() { queue ql; int vis[INF] = { 0}, dis[INF], pre[INF] = { 0}; ql.push (SS); memset (dis, 0x3f, sizeof dis); vis[SS] = 1, dis[SS] = 0; while (!ql.empty() ) { int x = ql.front(); ql.pop(); for (int i = head[x]; i != 0; i = edge[i].next) { if (edge[i].t == 0) continue; int v = edge[i].v, c = edge[i].c; if (dis[v] > dis[x] + c) { dis[v] = dis[x] + c; pre[v] = i; if (!vis[v]) ql.push (v), vis[v] = 1; } } vis[x] = 0; } min_dis = min (min_dis, dis[ST]); if (dis[ST] == Maxn) return 0; else { min_cost += dis[ST]; int k = pre[ST]; int cur_flow = Maxn; while (k) { if (cur_flow > edge[k].t) cur_flow = edge[k].t; G[edge[k].u][edge[k].v] = G[edge[k].v][edge[k].u] = 1 ^ G[edge[k].v][edge[k].u]; edge[k].t = edge[k ^ 1].t, edge[k].c = abs (edge[k].c); edge[k ^ 1].t = 0, edge[k ^ 1].c = -abs (edge[k ^ 1].c); k = pre[edge[k].u]; } max_flow += cur_flow; k = pre[ST]; while (k) { edge[k].t -= cur_flow, edge[k ^ 1].t += cur_flow; k = pre[edge[k].u]; } return 1; }}void dfs (int x) { for (int i = head[x]; i != 0; i = edge[i].next) { if (G[x][edge[i].v] && edge[i].t > 0 && edge[i].v < T) { edge[i].t = 0; dfs (edge[i].v); break; } } if (x == S) printf ("%d", x); else printf (" %d", x);}int MCMF() { while (SPFA() ); if (max_flow == 2 && min_cost == 2 * min_dis) { dfs (T); putchar (10); dfs (T); } else puts ("No solution");}void build() { scanf ("%d %d", &n, &m); int x, y, z; for (int i = 1; i <= m; i++) { scanf ("%d %d %d", &x, &y, &z); addEdge (x, y, 1, z); } S = 1, T = n; SS = n + 1, ST = n + 2; addEdge (SS, S, 2, 0), addEdge (T, ST, 2, 0);}int main() { build(); MCMF(); return 0;}