POJ2135：Farm Tour

题意：给定一个无向图，从1走到n再从n走回1，每个边只能走一遍，求最短路

题解：可以定义一个源点s，和一个汇点t

s和1相连容量为2，费用为0，

t和n相连容量为2，费用为0

然后所用的边的容量都定为1，跑一遍最小费用最大流即可

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 #include<vector>
  7 #define MAXN 1000+10
  8 #define INF 0x7f7f7f7f
  9 #define ll long long
 10 using namespace std;
 11 struct Edge{
 12     int from,to,cap,flow,cost;
 13     Edge(int u=0,int v=0,int c=0,int f=0,int w=0){
 14         from=u,to=v,cap=c,flow=f,cost=w;
 15     }
 16 };
 17 int n,m;
 18 vector<Edge> edges;
 19 vector<int> G[MAXN];
 20 int d[MAXN];
 21 int b[MAXN];
 22 int a[MAXN];
 23 int p[MAXN];
 24 void AddEdge(int u,int v,int cap,int cost){
 25     edges.push_back(Edge(u,v,cap,0,cost));
 26     edges.push_back(Edge(v,u,0,0,-cost));
 27     int t=edges.size();
 28     G[u].push_back(t-2);
 29     G[v].push_back(t-1);
 30 }
 31 int SPFA(int s,int t,int &flow,ll &cost){
 32     memset(d,0x7f,sizeof(d));
 33     memset(b,0,sizeof(b));
 34 
 35     queue<int> q;
 36     q.push(s);
 37     b[s]=1;
 38     d[s]=0;
 39     a[s]=INF;
 40     p[s]=0;
 41 
 42     while(!q.empty()){
 43         int x=q.front(); q.pop();
 44         b[x]=0;
 45         for(int i=0;i<G[x].size();i++){
 46             Edge& e=edges[G[x][i]];
 47             if(e.cap>e.flow&&d[e.to]>d[x]+e.cost){
 48                 d[e.to]=d[x]+e.cost;
 49                 a[e.to]=min(a[x],e.cap-e.flow);
 50                 p[e.to]=G[x][i];
 51                 if(!b[e.to]){
 52                     b[e.to]=1;
 53                     q.push(e.to);
 54                 }
 55             }
 56         }
 57     }
 58     if(d[t]==INF){
 59         return 0;
 60     }    
 61 
 62     flow+=a[t];
 63     cost+=1LL*a[t]*d[t];
 64     for(int x=t;x!=s;x=edges[p[x]].from){
 65         edges[p[x]].flow+=a[t];
 66         edges[p[x]^1].flow-=a[t];
 67     }
 68     return 1;
 69 }
 70 ll MincostMaxflow(int s,int t){
 71     int flow=0;
 72     ll cost=0;
 73     while(SPFA(s,t,flow,cost));
 74     return cost;
 75 }
 76 void solve(){
 77     printf("%lld
",MincostMaxflow(1,n+2));
 78 }
 79 void init(){
 80     memset(a,0,sizeof(a));
 81     memset(p,0,sizeof(p));
 82     edges.clear();
 83     for(int i=0;i<=n;i++){
 84         G[i].clear();
 85     }    
 86     for(int i=1;i<=m;i++){
 87         int u,v,w;scanf("%d%d%d",&u,&v,&w);
 88         u++,v++;
 89         AddEdge(u,v,1,w);
 90         AddEdge(v,u,1,w);
 91     }
 92     AddEdge(1,2,2,0);
 93     AddEdge(n+1,n+2,2,0);
 94 }
 95 int main()
 96 {
 97     while(~scanf("%d%d",&n,&m)){
 98         init();
 99         solve();
100     }
101     return 0;
102 }