百度里有很多大牛对这道题写了博客，但代码里没解释，我花了好几天才弄懂了这算法，现写下来给各位fish作参考，可更容易明白。
/*poj2135 */
#include<stdio.h>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#define M 10002
#define inf 1<<30
using namespace std;
struct Edge{
    int u,v;
    int c,f;
    int next;
 }edge[4*M];
 int pre[1002],p[1002];  //pre[]的用处在构造邻接边中，p[]记录路线
 int tot,n,m;
 int dist[1002],vist[1002];//用在spfa中，分别为：记录源点0到各点的最短距离(即费用),访问标记
 void add(int u,int v,int c,int f)
 {
    Edge e = {u,v,c,f,pre[u]}; //pre[u]是记录前一条edge中：开始点为u的边的值
    edge[tot] = e;
    pre[u] = tot++;   //更新pre[u]=tot ,tot++
}
void addedge2(int u,int v,int c,int f)
{
    add(u ,v ,c ,f); //正向的边，
    add(v,u,-c,0);  //对应的反向边，费用为-c,流量为0
}
 bool spfa()    //寻找费用最小的可增广路,spfa算法
 {
    int u,v;
    queue<int>que;
    memset(p,-1,sizeof(p));
    memset(vist,0,sizeof(vist));
    fill(&dist[0],&dist[1002],inf);//不能用 memset(dist,inf,sizeof(dist));或用for等
    vist[0]=1;dist[0]=0;
    que.push(0);
    while(!que.empty()){
        u=que.front();que.pop();vist[u]=0;//取出队头元素
        for(int i=pre[u];i!=-1;i=edge[i].next){ //与u相接的所有边
            if(edge[i].f){     //有流量
                v=edge[i].v;
                if(dist[v]>dist[u]+edge[i].c){  //调整
                  dist[v]=dist[u]+edge[i].c;
                  p[v]=i;//记录路线
                  if(!vist[v])que.push(v);  //入队
                }
            }
        }
    }
    return dist[n+1]!=inf;
 }
 int cost()   //因这题路的流量为1，不用求流量了
 {
    int ans=0,x;
    while(spfa()){
        ans+=dist[n+1];
        x=p[n+1];
        while(x!=-1){
            edge[x].f-=1;  //正边
            edge[x^1].f+=1;  //反边
            x=p[edge[x].u];  //x变为连接到 edge[x].u的边
        }
    }
    return ans;
 }
 int main()
 {
    int i,a,b,c;
    scanf("%d %d",&n,&m);
    memset(pre,-1,sizeof(pre)); tot=0;
    addedge2(0,1,0,2);       //增加源点0，汇点n+1,
    addedge2(n,n+1,0,2);
    for(i=0;i<m;i++){
        scanf("%d %d %d",&a,&b,&c);
        addedge2(a,b,c,1);
        addedge2(b,a,c,1);
    }
    printf("%d\n",cost());
    return 0;
 }


/* void addedge2(int u,int v,int c,int f)
 {
    Edge e = {u,v,c,f,pre[u]};
    edge[tot]=e; //正向的边，pre[u]是记录前一条edge中：开始点为u的边的值
    pre[u]=tot++;       //更新pre[u]=tot ,tot++
    Edge e = {v,u,-c,0,pre[v]};
    edge[tot]=e;  //对应的反向边，费用为-c,流量为0
    pre[v]=tot++;
 }   */ //这有语法错误  948K 63MS

• Re:纪念一下第一道最小费用最大流 (2597) scau200930760204 2010-08-27 15:33:09