题意：
FJ有n个农场，要从1号农场走到n号，再从n号走到1号（回来的路不能重复，不一定走完所有景点，只要求从1到n即可），给你一些景点之间的路的长度（双向），问你最短需要走多少路才能回来？
题解：
不同于双调旅行商问题（dp），因为距离不符合单调性。
用最小费用流，还是很裸的~
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 6 #define N 1010 7 #define M 100100 8 9 using namespace std; 10 11 int to[M],next[M],len[M],w[M],from[M],head[N],pre[N],n,m,S,T,dis[N],q[M<<4],cnt; 12 bool vis[N]; 13 14 inline void add(int u,int v,int wp,int p) 15 { 16 from[cnt]=u; to[cnt]=v; w[cnt]=wp; len[cnt]=p; next[cnt]=head[u]; head[u]=cnt++; 17 from[cnt]=v; to[cnt]=u; w[cnt]=-wp; len[cnt]=0; next[cnt]=head[v]; head[v]=cnt++; 18 } 19 20 void read() 21 { 22 memset(head,-1,sizeof head); 23 cnt=0; 24 for(int i=1,a,b,c;i<=m;i++) 25 { 26 scanf("%d%d%d",&a,&b,&c); 27 add(a,b,c,1); add(b,a,c,1); 28 } 29 S=0; T=n+1; 30 add(S,1,0,2); add(n,T,0,2); 31 } 32 33 bool spfa() 34 { 35 memset(dis,0x3f,sizeof dis); 36 memset(pre,-1,sizeof pre); 37 int h=1,t=2,sta; 38 q[1]=S; vis[S]=true; dis[S]=0; 39 while(h<t) 40 { 41 sta=q[h++]; 42 vis[sta]=false; 43 for(int i=head[sta];~i;i=next[i]) 44 if(len[i]>0&&dis[to[i]]>dis[sta]+w[i]) 45 { 46 dis[to[i]]=dis[sta]+w[i]; 47 pre[to[i]]=i; 48 if(!vis[to[i]]) 49 { 50 vis[to[i]]=true; 51 q[t++]=to[i]; 52 } 53 } 54 } 55 if(pre[T]==-1) return false; 56 else return true; 57 } 58 59 inline void updata() 60 { 61 for(int i=pre[T];~i;i=pre[to[i^1]]) 62 { 63 len[i]-=1; len[i^1]+=1; 64 } 65 } 66 67 void get_fee() 68 { 69 int ans=0; 70 while(spfa()) 71 { 72 ans+=dis[T]; 73 updata(); 74 } 75 printf("%d\n",ans); 76 } 77 78 int main() 79 { 80 while(scanf("%d%d",&n,&m)!=EOF) 81 { 82 read(); 83 get_fee(); 84 } 85 return 0; 86 }