POJ 2135 Farm Tour （最小费用最大流模版）

// // main.cpp // Richard // // Created by 邵金杰 on 16/8/16. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxV=10100; const int maxE=1000100; const int INF=1000000000; struct edge{ int from,to,c,cost,next; }; edge edges[maxE]; int dist[maxV],pre[maxV],head[maxV];; int total; void add(int u,int v,int c,int cost) { edges[total].from=u; edges[total].to=v; edges[total].c=c; edges[total].cost=cost; edges[total].next=head[u]; head[u]=total++; edges[total].from=v; edges[total].to=u; edges[total].c=0; edges[total].cost=-cost; edges[total].next=head[v]; head[v]=total++; } bool spfa(int s,int t) { memset(pre,-1,sizeof(pre)); for(int i=0;i<=t;i++) dist[i]=INF; dist[s]=0; queue<int> q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edges[i].next) { if(edges[i].c>0) { int v=edges[i].to; if(dist[v]>dist[u]+edges[i].cost) { dist[v]=dist[u]+edges[i].cost; pre[v]=i; q.push(v); } } } } return dist[t]!=INF; } int solve(int s,int t) { int mindist=0,flow; int flowsum=0; while(spfa(s,t)) { flow=INF; for(int i=pre[t];i!=-1;i=pre[edges[i].from]) { flow=min(flow,edges[i].c); } flowsum+=flow; for(int i=pre[t];i!=-1;i=pre[edges[i].from]) { edges[i].c-=flow; edges[i^1].c+=flow; } mindist+=dist[t]; } return mindist; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(head,-1,sizeof(head)); total=0; int a,b,c; add(0,1,2,0); add(n,n+1,2,0); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,1,c); add(b,a,1,c); } printf("%d\n",solve(0,n+1)); } return 0; }