SGU 185 Two shortest 最短路+最小费用最大流 或者 最短路+最大流
真心服了此题了
此题最贱之处在于内存只给了4M，也就是你只能开100W左右的int
我开了各种short 最后发现 short会莫名其妙变成4字节的去
然后就杯具了，MLE，开小了就会RE
这题明显不能用裸费用流去做了，裸费用流加的边太多了。任意两个点之间都来俩边的话一下子就给超内存了。
所以只好用最短路+费用流的方法去做。
不想写最短路+最大流的原因是 因为我的最大流模板太臃肿了 ，虽然至今没被卡过时，但是还是编程复杂度太高
于是决定偷了庄神 lost神牛的ISAP模板一个 http://www.zlinkin.com/?p=34 以后改造一下自己用
目测很短吧， 那是因为使用DFS的原因，而我那个模板是BFS无递归版本的。
#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <queue>#include <map>#include <set>#define eps 1e-5#define MAXN 404#define MAXM 160005#define INF 10007using namespace std;struct EDGE{ short v, cap, cost; int next;} edge[MAXM];int n, m, ans, flow, src, des;int e, head[MAXN];int que[MAXN], pre[MAXN], dis[MAXN];bool vis[MAXN];short g[MAXN][MAXN];void init(){ e = ans = flow = 0; memset(head, -1, sizeof(head));}void add(short u, short v, short cap, short cost){ edge[e].v = v; edge[e].cap = cap; edge[e].cost = cost; edge[e].next = head[u]; head[u] = e++;}void addEdge(short u, short v, short cap, short cost){ add(u, v, cap, cost); add(v, u, 0, -cost);}bool spfa(){ int i, h = 0, t = 1; for(i = 0; i <= n; i ++) { dis[i] = 1000000007; vis[i] = false; } dis[src] = 0; que[0] = src; vis[src] = true; while(t != h) { int u = que[h++]; h %= n; vis[u] = false; for(i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(edge[i].cap && dis[v] > dis[u] + edge[i].cost) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]) { vis[v] = true; que[t++] = v; t %= n; } } } } if(dis[des] == 1000000007) return false; return true;}void end(){ int u, p; short mi = 100; for(u = des; u != src; u = edge[p ^ 1].v) { p = pre[u]; mi = min(mi, edge[p].cap); } for(u = des; u != src; u = edge[p ^ 1].v) { p = pre[u]; edge[p].cap -= mi; edge[p ^ 1].cap += mi; ans += mi * edge[p].cost; // cost记录的为单位流量费用，必须得乘以流量。 } flow += mi;}int nt;void build1(){ short x, y, w; scanf("%d%d", &nt, &m); for(int i = 1; i <= m; i++) { scanf("%hd%hd%hd", &x, &y, &w); add(x, y, 1, w); add(y, x, 1, w); g[x][y] = g[y][x] = w; } src = 1; des = nt; n = des;}void build2(){ for(short i = 1; i <= nt; i++) for(short j = 1; j <= nt; j++) if(g[i][j] && dis[i] + g[i][j] == dis[j]) { addEdge(i, j, 1, g[i][j]); // printf("%d %d\n", i, j); } src = nt + 1; des = nt + 2; n = des; addEdge(src, 1, 2, 0); addEdge(nt, des, 2, 0);}void get(){ init(); build1(); spfa();}void MCMF2(){ init(); build2(); while(spfa()) end();}int flag;void dfs(int u){ printf(" %d", u); if(u == nt) { printf("\n"); flag = 1; return; } for(int i = head[u]; i != -1 && !flag; i = edge[i].next) if(edge[i].cap == 0 && i % 2 == 0) { if(edge[i].v > nt) return; edge[i].cap = -1; dfs(edge[i].v); }}int main(){ get(); int tmp = dis[des]; //printf("%d\n", tmp); MCMF2(); //printf("%d %d\n", tmp, ans); if(tmp * 2 == ans) { for(int i = head[1]; i != -1; i = edge[i].next) if(edge[i].cap == 0 && i % 2 == 0) { flag = 0; printf("1"); dfs(edge[i].v); } } else printf("No solution\n"); return 0;}