POJ 2135 Farm Tour 最小費用最大流

       題意：FJ帶朋友參觀自己的農場，從自己的房子出發到barn（谷倉、畜棚或車庫），再從barn傳回自己的房子，要求去回不走同一條路。

建圖：取超級源點，并與房子連一條邊，容量為2；取barn與超級彙點間的邊的容量為2，中間的建圖方法如代碼。

代碼：

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