题意: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](该路径上的能通过的最大的流*每单位流量的费用)