最小费用最大流

题意：有n个地点，m部船（m>=n），给出每部船到每个地点的时间。然后要派船到地点。每个船只能用一次即只能去只能去一个地方，每个地方只需要一部船。算出最小平均时间。要算平均时间其实就是算总时间最小，然后除以n即可。那怎么求总时间最小呢？

其实一看，就是匹配类型的问题，但是就我目前学的匹配的算法，没有可以解这道题的，然后是出于白书的图论专题，就考虑是不是可以转化为其他类型的问题来解呢？想起二分图最大匹配问题可以转化为最大流来解，所以很快就想到了用最小费用最大流来解

船从1到m标号，地点从m+1到m+n标号。建立有向图，都是从u船指向v地点，单位费用就是u船到v地点的时间，容量就是1.然后设立一个源点0,0指向所有的船，一共m条边，容量都是1，单位费用都是0.设立一个汇点m+n+1，所有地点指向汇点，单位费用为0容量为1.求源点0到汇点m+n+1的最小费用最大流。可知，最后最大流量为n，最小费用就是最小的总时间，然后除以n即可

这样设立就可以做到每部船和每个地点都只会被用一次（因为最大流满流的边不会再经过，而边容量是1，用一次就会满流）

建图后，直接最小费用最大流模板上去即可

因为是有向图，而且此题不会有平行边，所以邻接矩阵就可以，不用邻接表

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define MAX 50#define INF 1000000000.00000#define eps 1e-8int n,m,F;double C;double g[MAX][MAX],cost[MAX][MAX],d[MAX];int cap[MAX][MAX],flow[MAX][MAX],p[MAX];void init(){    memset(cap,0,sizeof(cap));    memset(flow,0,sizeof(flow));    memset(cost,0,sizeof(cost));    for(int i=1; i<=n; i++)        for(int j=1; j<=m; j++)        {            int u,v;            u=j; v=m+i;            cap[u][v]=1;            scanf("%lf",&cost[u][v]);            cost[v][u]=-cost[u][v];        }    for(int i=1; i<=m; i++)        cap[0][i]=1;    for(int i=m+1; i<=m+n; i++)        cap[i][m+n+1]=1;}int relax(int u ,int v){    if(d[v]>d[u]+cost[u][v]+eps)  //精度        return 1;    else         return 0;}void spfa(int s ,int t){    queue
         
          q;    int vis[MAX];    for(int i=0; i<=m+n+1; i++)    { d[i]=INF; vis[i]=0; p[i]=-1; }    d[s]=0; vis[s]=1;    q.push(s);    while(!q.empty())    {        int u;        u=q.front(); vis[u]=0; q.pop();        for(int v=0; v<=m+n+1; v++)            if(flow[u][v]
          
           < cap[p[u]][u]-flow[p[u]][u] ? min : cap[p[u]][u]-flow[p[u]][u]; for(u=t; u!=s; u=p[u]) //增广 { flow[p[u]][u]+=min; flow[u][p[u]]-=min; } F+=min; C+=1.*min*d[t]; } //printf("%.2lf\n",C); //printf("%d\n",F); printf("%.2f\n",C/n+eps); //卡精度 return ;}int main(){ while(scanf("%d%d",&n,&m)) { if(!n && !m) break; init(); mincost_maxflow(); } return 0;}