POJ 2135 Farm Tour（最小费用最大流，变形）

题意：给一个无向图，FJ要从1号点出发到达n号点，再返回到1号点，但是路一旦走过了就会销毁（即回去不能经过），每条路长度不同，那么完成这趟旅行要走多长的路？（注：会有重边，点号无序，无向图！）

思路：

　　有重边，要用邻接表。所给的每条边都要变成4条有向边！否则可能一开始就到达不了终点了。最后要再加上一个源点和汇点，容量cap（源点，1）=2，指定只能走两次，再规定其他所给的边的容量是1就行了，当边被走过了，就自动增加了流，也就走不了了。

　　解释看代码更清晰。

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #include <stack>

 #include <algorithm>

 #include <map>

 //#include <bits/stdc++.h>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x7f7f7f7f

 using namespace std;

 const int N=+;

 vector<int> vect[N];

 struct node

 {

     int from;

     int to;

     int cost;

     int cap;

     int flow;

 }edge[N*];     //边数是4*M的大小

 int edge_num;   //边的上限

 int f[N];       //流

 int path[N];    //记录路径

 int c[N];       //记录费用

 bool in[N];     //是否在queue中

 void add_node(int a, int b, int c, int ca, int fl)

 {

     edge[edge_num].from=a;

     edge[edge_num].to=b;

     edge[edge_num].cost=c;

     edge[edge_num].cap=ca;

     edge[edge_num].flow=fl;

     vect[a].push_back(edge_num++);

 }

 LL spfa(int s,int e)

 {

     deque<int> que;

     que.push_back(s);

     c[s]=;

     f[s]=INF;

     in[s]=;

     while(!que.empty())

     {

         int x=que.front();

         que.pop_front();

         in[x]=;

         for(int i=; i<vect[x].size(); i++)

         {

             node t=edge[vect[x][i]];

             if(t.cap>t.flow && c[t.to]>c[t.from]+t.cost)  //能流过,且费用更小即可更新。

             {

                 path[t.to]=vect[x][i];          //记边号，方便更新flow

                 c[t.to]=c[t.from]+t.cost;       //更新cost，相当于距离

                 f[t.to]=min(f[t.from], t.cap-t.flow);

                 if(!in[t.to])

                 {

                     que.push_back(t.to);

                     in[t.to]=;

                 }

             }

         }

     }

     return c[e];

 }

 int m;

 int mcmf(int s, int e)

 {

     LL ans=;

     while()

     {

         memset(f, , sizeof(f));

         memset(c, 0x7f, sizeof(c));

         memset(in, , sizeof(in));

         memset(path, , sizeof(path));

         int tmp=spfa(s, e);

         if(tmp==INF)    return ans;

         ans+=tmp*f[e];   //这是最小费用。注：每次的流可能不是1。

         int ed=e;

         while(ed!=s)

         {

             int en=path[ed];

             edge[en].flow+=f[e];

             edge[en^].flow-=f[e];

             ed=edge[en].from;

             //cout<<edge[en].from<<"-"<<edge[en].to<<endl;

         }

     }

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int  n, a, b, c;

     while(~scanf("%d%d", &n, &m))

     {

         for(int i=n*; i>=; i--)   vect[i].clear();

         edge_num=;

         for(int i=; i<m; i++)

         {

             scanf("%d%d%d",&a,&b,&c);

             add_node(a,b,c,,);    //4条有向边。

             add_node(b,a,-c,,);

             add_node(b,a,c,,);

             add_node(a,b,-c,,);

         }

         add_node(,,,,);        //加多2条边

         add_node(,,,,);        //加这条无意义，但是更新flow时更方便

         add_node(n,n+,,,);

         add_node(n+,n,,,);

         printf("%lld\n",mcmf(, n+));

     }

     return ;

 }

AC代码