最小费用最大流

思想：
采用贪心的思想。通过SPFA，增广路的思想，每次找到一条从源点到达汇点的花费最小的路径

 1  if(e.flow>0&&dis[e.v]>dis[now]+e.cost)
 2             {
 3                 dis[e.v]=dis[now]+e.cost; //维护最小费用
 4                 addflow[e.v]=min(addflow[now],e.flow);//维护流量
 5                 pre[e.v]=i;//将点指向上一条边，方便回溯
 6  
 7                 if(!vis[e.v])
 8                 {
 9                     q.push(e.v);
10                     vis[e.v]=1;
11                 }
12             }

增加流量，直到无法找到一条从源点到达汇点的路径，算法结束。每次找一条花费最小的路径，从源点跑到汇点，然后维护这条路上所加的流量最小值（addflow函数）,然后总流量加上流量。最后再回溯，将正向边减去，反向边加上流量。找到一条路径。再while循环这个过程，直到找不到S到T的点；这样每次找的边都保证费用最小，每次增加流量，直到没有路径增加，得到最小费用最大流；

回溯算法如下：

1  while(now!=s)
2     {
3         edg[pre[now]].flow-=addflow[t];
4         edg[pre[now]^1].flow+=addflow[t];
5         now=edg[pre[now]].u;
6     }

View Code

由于最大流量有限，每执行一次循环流量都会增加，因此该算法肯定会结束，且同时流量也必定会达到网络的最大流量；同时由于每次都是增加的最小的花费，即当前的最小花费是所有到达当前流量flow时的花费最小值，因此最后的总花费最小。

板子如下：

原题为：

问题D：海上采矿站

时间限制： 1秒内存限制： 128 MB

题目描述

海洋是资源的宝库，人类社会的发展越来越依赖于它。为了开发和利用海洋资源，有必要在海上建立采矿站。然而，由于海底矿物资源，海洋中的无线电信号通常很弱，以至于并非所有采矿站都能进行直接通信。然而，通信是必不可少的，每两个采矿站必须能够相互通信（直接或通过其他一个或多个采矿站）。为了满足将开采资源运到陆地投入使用的需要，沿海岸相应建设n个港口，每个港口可以直接与一个或多个采矿站通信。

由于一些采矿站不能直接相互通信，为了船舶导航的安全，船只只允许在可以直接相互通信的采矿站之间航行。

采矿是艰巨的，人们做这项工作需要适当的休息（也就是说，让船只返回港口）。但真是巧合！这次，n艘采矿船只轮流在同一时间休息。它们分散在不同的站点，现在它们必须返回港口，此外，一个港口只能容纳一艘船。现在所有船只将开始返回，如何选择他们的航行路线，使他们的航行路线的总和最小。

请注意，一旦船舶进入港口，它就不会出来！

输入

有几个测试用例。每个测试用例以一行中的四个整数开始，n（1 = <n <= 100），m（n <= m <= 200），k和p。n表示n个船只和n个港口，m表示m个采矿站，k表示k个边缘，每个边缘对应于li在采矿站和另一个采矿站之间的nk，p表示p个边缘，每个边缘指示link在港口和采矿站之间。以下行是n个整数，每个整数表示一个船只所属的一个站点。然后是k行，每行包括3个整数a，b和c，表明在采矿站a和b之间存在直接通信并且它们之间的距离是c。最后，接着是另外的p行，每行包括3个整数d，e和f，表明端口d和采矿站e之间存在直接通信，它们之间的距离为f。此外，采矿站由1到m的数字和端口1到n表示。输入由文件结束终止。

输出

每个测试用例输出其航行路线的最小总和。

样例输入

样例输出

  1 #include<bits/stdc++.h>
  2 #define INF INT_MAX/2
  3 #define N 310
  4 using namespace std;
  5  
  6 typedef struct
  7 {
  8     int u,v,next;
  9     int flow,cost;
 10 }ss;
 11  
 12 ss edg[N*N*4];
 13 int head[N];
 14 int now_edge=0;
 15  
 16 void init()
 17 {
 18     memset(head,-1,sizeof(head));
 19     now_edge=0;
 20 }
 21  
 22 void inline addedge(int u,int v,int flow,int cost)
 23 {
 24     edg[now_edge]=(ss){u,v,head[u],flow,cost};
 25     head[u]=now_edge++;
 26     edg[now_edge]=(ss){v,u,head[v],0,-cost};
 27     head[v]=now_edge++;
 28 }
 29  
 30  
 31 int dis[N];
 32 int vis[N]={0};
 33 int addflow[N]={0};
 34 int pre[N]={0};
 35 queue<int>q;
 36  
 37 bool spfa(int s,int t,int &flow,int &cost)
 38 {
 39     for(int i=0;i<N;i++)
 40     {
 41         dis[i]=INF;
 42         vis[i]=0;
 43     }
 44  
 45     while(!q.empty())q.pop();
 46     dis[s]=0;
 47     vis[s]=1;
 48     q.push(s);
 49     addflow[s]=INF;
 50     while(!q.empty())
 51     {
 52         int now=q.front();
 53         q.pop();
 54         vis[now]=0;
 55  
 56         for(int i=head[now];i!=-1;i=edg[i].next)
 57         {
 58             ss e=edg[i];
 59  
 60             if(e.flow>0&&dis[e.v]>dis[now]+e.cost)
 61             {
 62                 dis[e.v]=dis[now]+e.cost;
 63                 addflow[e.v]=min(addflow[now],e.flow);
 64                 pre[e.v]=i;
 65  
 66                 if(!vis[e.v])
 67                 {
 68                     q.push(e.v);
 69                     vis[e.v]=1;
 70                 }
 71             }
 72         }
 73     }
 74  
 75     if(dis[t]==INF)return false;
 76  
 77     flow+=addflow[t];
 78     cost+=addflow[t]*dis[t];
 79  
 80     int now=t;
 81     while(now!=s)
 82     {
 83         edg[pre[now]].flow-=addflow[t];
 84         edg[pre[now]^1].flow+=addflow[t];
 85         now=edg[pre[now]].u;
 86     }
 87  
 88     return true;
 89 }
 90  
 91 void MCMF(int s,int t,int &flow,int &cost)
 92 {
 93     while(spfa(s,t,flow,cost));
 94 }
 95  
 96  
 97  
 98 int main()
 99 {
100     int n,m,p,k;
101     while(scanf("%d %d %d %d",&n,&m,&k,&p)==4)
102     {
103         init();
104         int s=n+m+1;
105         int t=s+1;
106  
107         for(int i=1;i<=n;i++)
108         {
109             int a;
110             scanf("%d",&a);
111             addedge(s,a+n,1,0);
112         }
113  
114         while(k--)
115         {
116             int u,v,w;
117             scanf("%d %d %d",&u,&v,&w);
118             addedge(n+u,n+v,INF,w);
119             addedge(n+v,n+u,INF,w);
120         }
121  
122         while(p--)
123         {
124             int u,v,w;
125             scanf("%d %d %d",&u,&v,&w);
126             addedge(n+v,u,INF,w);
127         }
128  
129         for(int i=1;i<=n;i++)addedge(i,t,1,0);
130         int flow=0,cost=0;
131         MCMF(s,t,flow,cost);
132         printf("%d
",cost);
133     }
134  
135     return 0;
136 }