POJ 2135 Farm Tour 最小费用最大流

题意：FJ带朋友参观自己的农场，从自己的房子出发到barn（谷仓、畜棚或易做图），再从barn返回自己的房子，要求去回不走同一条路。

建图：取超级源点，并与房子连一条边，容量为2；取barn与超级汇点间的边的容量为2，中间的建图方法如代码。

代码：

[cpp]
#include<iostream>
#include<queue>
#define maxe 400005
#define maxn 1005
#define INF 0x7fffffff
using namespace std;
struct Edge
{
       int v,next;
       int p,f;
       Edge(int vv,int pp,int ff,int x):v(vv),p(pp),f(ff),next(x){}
       Edge(){}
} e[maxe];
int dist[maxn],vis[maxn],cur[maxn];
int size,pre[maxn],head[maxn],mimf;
/*
最小费用最大流：
用最短路算法在图上找到一条最小费用的增广路径
因为流量可以回退，即有负值边，采用SPFA或者Bellman_Ford。
在找到的最短路上面修改流量（跟最大流算法一致）
每条路径的费用为 mimf*dist[T]（该路径上的能通过的最大的流*每单位流量的费用）
所有路径的费用之和就是总的最小费用。
*/
void AddEdge(int u,int v,int p,int f)
{

     e[size]=Edge(v,p,f,head[u]);
     head[u]=size++;
     e[size]=Edge(u,-p,0,head[v]);
     head[v]=size++;
}
bool SPFA(int s,int t,int n)
{
     int f,u,v,i;
     queue<int> que;
     while( !que.empty()) que.pop();
     memset(vis,0,sizeof(vis));
     memset(dist,0x7f,sizeof(dist));
     memset(pre,-1,sizeof(pre));

     que.push(s), vis[s]=true, dist[s]=0;

     while( !que.empty()){

            u=que.front();
            que.pop(), vis[u]=false;

            for( i=head[u];i!=-1;i=e[i].next){
                 v=e[i].v;
                 if( e[i].f&&dist[v]>dist[u]+e[i].p){

                     dist[v]=dist[u]+e[i].p;
                     pre[v]=u;
                     cur[v]=i;
                     /* pre,cur数组记录路径*/
                     if( !vis[v]){
                         que.push(v);
                         vis[v]=1;
                     }
                 }
            }

     }
     if(pre[t]==-1) return false;
     return true;
}
void Update(int u) //在找到的最小费用增广路径上修改流量
{
     if(pre[u]==-1) return ;
     if( mimf>e[cur[u]].f) mimf=e[cur[u]].f;
     Update(pre[u]);
     e[cur[u]].f-=mimf;
     e[cur[u]^1].f+=mimf;
}
int main()
{
    int n,m,a,b,c,ans;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    size=0;
    while( m--){
           scanf("%d%d%d",&a,&b,&c);
           AddEdge(a,b,c,1);   //因为是无向图，将两条边。
           AddEdge(b,a,c,1);
    }
    AddEdge(0,1,0,2);
    AddEdge(n,n+1,0,2);
    ans=0;
    while( SPFA(0,n+1,n)){

           mimf=INF;
           Update(n+1);
           ans+=mimf*dist[n+1];
    }
    printf("%d\n",ans);

    return 0;
}

补充：软件开发 , C++ ,