首页 > 代码库 > POJ 2195 Going Home【最小费用流 二分图最优匹配】
POJ 2195 Going Home【最小费用流 二分图最优匹配】
题目大意：一个n*m的地图，上面有一些人man（m）和数量相等的house(H) 图上的距离为曼哈顿距离 问所有人住进一所房子（当然一个人住一间咯）距离之和最短是多少？思路：一个人一间房，明显是二分图的模型，边权为人和房子的曼哈顿距离，然后算一下最小距离即可 懒得学KM了 最小费用流的经典建图#include #include #include #include #include #define maxn 40000#define inf 0x3f3f3f3fusing namespace std;struct POINT{ int x; int y;}a[maxn],b[maxn];int head[maxn],root[maxn],point[maxn],next[maxn];int flow[maxn],cost[maxn],pre[maxn],now=0,dist[maxn];int n,m,h,h2;char ch[maxn];int mabs(int x){ return x>0?x:-x;}int distanc(int i,int j){ return mabs(a[i].x-b[j].x)+mabs(a[i].y-b[j].y);}void add(int x,int y,int v,int c){ next[++now]=head[x]; head[x]=now; point[now]=y; flow[now]=v; cost[now]=c; root[now]=x; next[++now]=head[y]; head[y]=now; point[now]=x; flow[now]=0; cost[now]=-c; root[now]=y;}int spfa(int s,int t){ memset(pre,0,sizeof(pre)); for(int i=0;i<=t;i++)dist[i]=inf; dist[s]=0; int visit[maxn]={0}; visit[s]=1; queueq; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); visit[u]=0; for(int i=head[u];i;i=next[i]) { int k=point[i]; if(dist[u]+cost[i]POJ 2195 Going Home【最小费用流 二分图最优匹配】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。