网络图中 每条边 多给出了 单位流量的费用 cost(u,v) ,当通过(u,v)的流量为 f ( u , v ) f(u,v) f(u,v)时,需要花费 f ( u , v ) ∗ c o s t ( u , v ) f(u,v)*cost(u,v) f(u,v)∗cost(u,v)
因为是在 最大流的前提下求出最小费用, 那么 最大流量已经确定了,即使每条边的花费不一样,但只要费用和最小就行了
HDU 1533
人作为一部分,房子作为一部分， 费用是坐标系下的距离,建一个源点和终点,源点和人连接,费用是0房子和终点同理所有边的流相同能够保证 人去房子的机会相等, =1便于费用计算 #include <iostream> #include <queue> #include <cstring> using namespace std; const int inf = 1e9+5; const int maxn = 1e5+5; struct Edge { int to,next,cost,c,flow; } edge[maxn]; int head[maxn],tot; int pre[maxn],dist[maxn]; bool vis[maxn]; char ch[110][110]; int x[210],y[210]; int n,m; void addedge(int u,int v,int c,int cost) { edge[tot].to = v; edge[tot].c = c; edge[tot].cost = cost; edge[tot].flow = 0; edge[tot].next = head[u]; head[u] = tot++; edge[tot].to = u; edge[tot].c = 0; edge[tot].cost = -cost; edge[tot].flow = 0; edge[tot].next = head[v]; head[v] = tot++; } bool spfa(int source,int sink) { queue<int> que; /* for (int i=0; i<=sink; ++i) {*/ //dist[i] = inf; //vis[i] = false; //pre[i] = -1; /*}*/ memset(dist,inf,sizeof dist); memset(vis,0,sizeof vis); memset(pre,-1,sizeof pre); dist[source] = 0; vis[source] = 1; que.push(source); while (!que.empty()) { int cur = que.front(); que.pop(); vis[cur] = false; for (int i=head[cur]; i!=-1; i=edge[i].next) { int v=edge[i].to; if (edge[i].c>edge[i].flow && dist[v]>dist[cur]+edge[i].cost) { dist[v] = dist[cur] + edge[i].cost; pre[v] = i; //点v的入边 if (!vis[v]) { vis[v] = 1; que.push(v); } } } } if (pre[sink] == -1) return false; return true; } void Dinic(int source,int sink,int &cost) { cost = 0; while (spfa(source,sink)) { int delta = inf; int i = pre[sink]; while (i != -1) { delta = min(delta,edge[i].c - edge[i].flow); i = pre[edge[i^1].to]; } i = pre[sink]; while (i != -1) { edge[i].flow += delta; edge[i^1].flow -= delta; cost += edge[i].cost * delta; // 已知流量一定是1,delta 可以无 i = pre[edge[i^1].to]; } } } int main() { while (scanf("%d%d",&n,&m) && (n+m)) { for (int i=0; i<n; ++i) scanf("%s",ch[i]); int num=0; for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) if (ch[i][j] == 'm') { ++num; x[num] = i; y[num] = j; } int cnt = 0; for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) if (ch[i][j] == 'H') { ++cnt; x[num+cnt] = i; y[num+cnt] = j; } int source=0,sink=num+cnt+1; memset(head,-1,sizeof head); tot = 0; for (int i=1; i<=num; ++i) addedge(source,i,1,0); for (int i=num+1; i<=num+cnt; ++i) addedge(i,sink,1,0); for (int i=1; i<=num; ++i) for (int j=1; j<=cnt; ++j) { int u = i,v = num+j; int c = abs(x[u]-x[v]) + abs(y[u] - y[v]); addedge(u,v,1,c); } //cout << "yes" <<endl; int cost; Dinic(source,sink,cost); //cout << "no" <<endl; printf("%d\n",cost); } return 0; }