POJ2135 最小费用最大流模板题

练练最小费用最大流

此外此题也是一经典图论题

题意：找出两条从s到t的不同的路径，距离最短。

　　要注意：这里是无向边，要变成两条有向边

#include <cstdio>

#include <cstring>

#define MAXN 1005

#define MAXM 10005

#define INF 0x3f3f3f3f

struct Edge

{

    int y,c,w,ne;//c容量 w费用

}e[MAXM*];

int n,m,x,y,w;

int s,t,Maxflow,Mincost;

int all,be[MAXN];

int q[MAXM*],dis[MAXN],pre[MAXN];//pre存的是当前点的前边

bool vis[MAXN];

void add(int x, int y, int c, int cost)

{

    e[all].y=y;e[all].c=c;e[all].w=cost;

    e[all].ne=be[x];

    be[x]=all++;

    e[all].y=x;e[all].c=;e[all].w=-cost;//反向边费用取负

    e[all].ne=be[y];

    be[y]=all++;

}

void init()

{

    all=;

    memset(be,-,sizeof(be));

}

bool spfa(int s, int t)

{

    for(int i=; i<MAXN; i++)

    {

        dis[i]=INF;

        vis[i]=;

        pre[i]=-;

    }

    dis[s]=;

    vis[s]=;

    int head=,tail=;

    q[++tail]=s;

    while(head<tail)

    {

        int u=q[++head];

        vis[u]=;

        for(int i=be[u]; i!=-; i=e[i].ne)

        {

            int v=e[i].y;

            if(e[i].c> && dis[v]>dis[u]+e[i].w)

            {

                dis[v]=dis[u]+e[i].w;

                pre[v]=i;

                if(!vis[v])

                {

                    vis[v]=;

                    q[++tail]=v;

                }

            }

        }

    }

    if(pre[t]==-) return ;

    return ;

}

void MincostMaxflow(int s, int t)

{

    Maxflow=;

    Mincost=;

    while(spfa(s,t))

    {

        int minc=INF;

        for(int i=pre[t]; i!=-; i=pre[e[i^].y])

            if(minc>e[i].c) minc=e[i].c;

        for(int i=pre[t]; i!=-; i=pre[e[i^].y])

        {

            e[i].c-=minc;

            e[i^].c+=minc;

            Mincost+=e[i].w*minc;

        }

        Maxflow+=minc;

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    init();

    s=n+;

    t=n+;

    for(int i=; i<m; i++)

    {

        scanf("%d%d%d",&x,&y,&w);

        add(x,y,,w);

        add(y,x,,w);

    }

    add(s,,,);

    add(n,t,,);

    MincostMaxflow(s,t);

    printf("%d\n",Mincost);

    return ;

}