这题卡精度 eps = 1e-6用起来
然后主要还是建图 有多个起点（警察 下标1 到 m）多个终点（银行 下标 m+1到n+m）
所以取源点0 建有向边到警察（m次建边）取终点（n+m+1）从银行到n+m+1建有向边（n次） 然后警察到银行建边（n*m次）最后模版
#include#include #include using namespace std; const int MAX = 102; #define eps 1e-6 int n,m; struct edge { int u; int v; int flow; int cap; double cost; int next; }e[10000]; double dis[MAX]; int first[MAX]; int p[MAX]; bool vis[MAX]; int edgenum; int f; double c; int s,t; void add(int u,int v,int cap,double w) { e[edgenum].u = u; e[edgenum].v = v; e[edgenum].flow = 0; e[edgenum].cap = cap; e[edgenum].cost = w; e[edgenum].next = first[u]; first[u] = edgenum++; e[edgenum].u = v; e[edgenum].v = u; e[edgenum].flow = 0; e[edgenum].cap = 0; e[edgenum].cost = -w; e[edgenum].next = first[v]; first[v] = edgenum++; } void EK() { queue q; c = f = 0; while(1) { for(int i = 0;i <= t; i++) dis[i] = (i == 0 0 : 999999999); memset(vis,false,sizeof(vis)); memset(p,-1,sizeof(p)); q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int k = first[u]; k != -1; k = e[k].next) { int v = e[k].v; if(e[k].cap > e[k].flow && dis[v] > dis[u] + e[k].cost + eps) { dis[v] = dis[u] + e[k].cost; p[v] = k; if(!vis[v]) { vis[v] = true; q.push(v); } } } } if(dis[t] == 999999999) break; int a = 999999999; for(int u = p[t]; u != -1; u = p[e[u].u]) a = min(a,e[u].cap - e[u].flow); for(int u = p[t]; u != -1; u = p[e[u].u]) { e[u].flow += a; e[u^1].flow -= a; } c += dis[t] * (double)a; f += a; } } int main() { int i,j; double k; while(scanf("%d %d",&n,&m),n||m) { edgenum = 0; s = 0; t = n+m+1; memset(first,-1,sizeof(first)); for(i = 1;i <= m; i++) add(0,i,1,0); for(i = 1; i <= n; i++) { for(j = 1;j <= m; j++) { int u = j; int v = m + i; scanf("%lf",&k); add(u,v,1,k); } } for(i = m + 1;i <= n + m; i++) add(i,t,1,0); EK(); printf("%.2f\n",c/n + eps); } return 0; }