POJ2135 Farm Tour（最小费用最大流）

题目问的是从1到n再回到1边不重复走的最短路，本质是找1到n的两条路径不重复的尽量短的路。

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define INF (1<<30)

 #define MAXN 111

 #define MAXM 2222

 struct Edge{

     int u,v,cap,cost,next;

 }edge[MAXM];

 int head[MAXN];

 int NV,NE,vs,vt;

 void addEdge(int u,int v,int cap,int cost){

     edge[NE].u=u; edge[NE].v=v; edge[NE].cap=cap; edge[NE].cost=cost;

     edge[NE].next=head[u]; head[u]=NE++;

     edge[NE].u=v; edge[NE].v=u; edge[NE].cap=; edge[NE].cost=-cost;

     edge[NE].next=head[v]; head[v]=NE++;

 }

 bool vis[MAXN];

 int d[MAXN],pre[MAXN];

 bool SPFA(){

     for(int i=;i<NV;++i){

         vis[i]=;

         d[i]=INF;

     }

     vis[vs]=;

     d[vs]=;

     queue<int> que;

     que.push(vs);

     while(!que.empty()){

         int u=que.front(); que.pop();

         for(int i=head[u]; i!=-; i=edge[i].next){

             int v=edge[i].v;

             if(edge[i].cap && d[v]>d[u]+edge[i].cost){

                 d[v]=d[u]+edge[i].cost;

                 pre[v]=i;

                 if(!vis[v]){

                     vis[v]=;

                     que.push(v);

                 }

             }

         }

         vis[u]=;

     }

     return d[vt]!=INF;

 }

 int MCMF(){

     int res=;

     while(SPFA()){

         int flow=INF,cost=;

         for(int u=vt; u!=vs; u=edge[pre[u]].u){

             flow=min(flow,edge[pre[u]].cap);

         }

         for(int u=vt; u!=vs; u=edge[pre[u]].u){

             edge[pre[u]].cap-=flow;

             edge[pre[u]^].cap+=flow;

             cost+=flow*edge[pre[u]].cost;

         }

         res+=cost;

     }

     return res;

 }

 int main(){

     int n,m,a,b,c;

     scanf("%d%d",&n,&m);

     vs=; vt=n+; NV=vt+; NE=;

     memset(head,-,sizeof(head));

     while(m--){

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

         addEdge(a,b,,c);

         addEdge(b,a,,c);

     }

     addEdge(vs,,,);

     addEdge(n,vt,,);

     printf("%d",MCMF());

     return ;

 }