Going Home （费用流）

题目链接：http://poj.org/problem?id=2195

题目大概：

模板来自 poursoul

在一个矩形地图中，有n个人要去n个房子里去，一个人每走一格花费1元，问最少花费为多少。

思路：

计算出n个人中的每个人与n个房子的距离w，然后开始建图。

s连每个人，容量为1，人连房子，容量为1，费用为w，房子连t，容量为1.

最后跑一遍费用流。

感想：

有时候可以把一个平面图转化成线性的点来解题。

代码：

#include 
#include 
#include 
#include 
#define clear(A, X) memset(A, X, sizeof A)
#define min(A, B) ((A) < (B) ? (A) : (B))
using namespace std;const int maxE = 2000000;
const int maxN = 256;
const int oo = 0x3f3f3f3f;struct Edge{int v, c, w, n;Edge(){}Edge(int V, int C, int W, int N) : v(V), c(C), w(W), n(N){}
};struct Node{int l, r, w;
};
struct poin
{int x,y;
}x1[300],x2[300];
Edge edge[maxE];
Node sche[maxN];
int adj[maxN], cntE;
int Q[maxE], head, tail;
int d[maxN], inq[maxN], cur[maxN], f[maxN];
int cost, flow, s, t;
int N, M, K;void addedge(int u, int v, int c, int w){edge[cntE] = Edge(v, c,  w, adj[u]); adj[u] = cntE++;edge[cntE] = Edge(u, 0, -w, adj[v]); adj[v] = cntE++;
}int spfa(){f[s] = oo;clear(d, oo);clear(inq, 0);cur[s] = -1;d[s] = 0;head = tail = 0;Q[tail++] = s;inq[s] = 1;while(head != tail){int u = Q[head++];inq[u] = 0;for(int i = adj[u]; ~i; i = edge[i].n){int v = edge[i].v, c = edge[i].c, w = edge[i].w;if(c && d[v] > d[u] + w){d[v] = d[u] + w;f[v] = min(f[u], c);cur[v] = i;if(!inq[v]){Q[tail++] = v;inq[v] = 1;}}}}if(d[t] == oo) return 0;flow += f[t];cost += d[t] * f[t];for(int i = cur[t]; ~i; i = cur[edge[i ^ 1].v]){edge[i].c -= f[t];edge[i ^ 1].c += f[t];}return 1;
}int MCMF(){flow = cost = 0;while(spfa());return cost;
}void init(){clear(adj, -1);cntE = 0;
}void getmap(){int cnt=0,ans=0;char s1[120][120];for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！