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 10007
using namespace std;
typedef int type;
struct EDGE
{
    int v, next;
    type w;
} edge[MAXM];
int head[MAXN], e;
inline void init()
{
    memset(head, -1, sizeof(head));
    e = 0;
}
inline void add(int u, int v, type w)
{
    edge[e].v = v;
    edge[e].w = w;
    edge[e].next = head[u];
    head[u] = e++;
    edge[e].v = u;
    edge[e].w = 0;
    edge[e].next = head[v];
    head[v] = e++;
}
int n;
int h[MAXN];
int gap[MAXN];
int src, des;
inline type dfs(int pos, type cost)
{
    if (pos == des) return cost;
    int j, minh = n - 1;
    type lv = cost, d;
    for (j = head[pos]; j != -1; j = edge[j].next)
    {
        int v = edge[j].v;
        type w = edge[j].w;
        if(w > 0)
        {
            if (h[v] + 1 == h[pos])
            {
                if (lv < edge[j].w) d = lv;
                else d = edge[j].w;
                d = dfs(v, d);
                edge[j].w -= d;
                edge[j ^ 1].w += d;
                lv -= d;
                if (h[src] >= n) return cost - lv;
                if (lv == 0) break;
            }
            if (h[v] < minh) minh = h[v];
        }
    }
    if (lv == cost)
    {
        --gap[h[pos]];
        if (gap[h[pos]] == 0) h[src] = n;
        h[pos] = minh + 1;
        ++gap[h[pos]];
    }
    return cost - lv;
}
type sap()
{
    type ret = 0;
    memset(gap, 0, sizeof(gap));
    memset(h, 0, sizeof(h));
    gap[0] = n;
    while (h[src] < n) ret += dfs(src, INF);
    return ret;
}

整个模板里先init初始化，然后src,des, n 自己指定， 一般标号从1开始

然后这题我先用了一次spfa

将最短路求出来

然后跑一次最小费用最大流，看是否等于最短路的二倍，然后DFS之类的。

建最小费用的图时，注意使用SPFA求出来的最短路边集去建立，就是dis[i] + g[i][j] = dis[j]这样的边

可以想到的是这样的边明显会比整个图的边要少一半以上 而不至于去MLE

#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 10007
using 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;
}