最小费用最大流
题意：有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 <cstdio> #include <cstring> #include <queue> #include <cmath> using namespace std; #define MAX 50 #define INF 1000000000.00000 #define eps 1e-8 int 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<int>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[u][v] && relax(u,v)) //松弛卡精度 { d[v]=d[u]+cost[u][v]; p[v]=u; if(!vis[v]) { vis[v]=1; q.push(v); } } } return ; } void mincost_maxflow() { int s=0,t=m+n+1; F=0; C=0; while(1) { spfa(s,t); if(d[t]==INF) break; int u,min=0x3f3f3f3f; for(u=t; u!=s; u=p[u]) min=min < 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; }