題意：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;
}
