POJ 2195 Going Home【最小费用流 二分图最优匹配】

题目大意:一个n*m的地图,上面有一些人man(m)和数量相等的house(H) 图上的距离为曼哈顿距离 问所有人住进一所房子(当然一个人住一间咯)距离之和最短是多少?
思路:一个人一间房,明显是二分图的模型,边权为人和房子的曼哈顿距离,然后算一下最小距离即可 懒得学KM了 最小费用流的经典建图

#include
#include
#include
#include
#include
#define maxn 40000
#define inf 0x3f3f3f3f
using 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;iq;
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【最小费用流 二分图最优匹配】

时间: 11-16

POJ 2195 Going Home【最小费用流 二分图最优匹配】的相关文章

POJ 2195 Going Home 最小费用流 裸题

给出一个n*m的图,其中m是人,H是房子,.是空地,满足人的个数等于房子数. 现在让每个人都选择一个房子住,每个人只能住一间,每一间只能住一个人. 每个人可以向4个方向移动,每移动一步需要1$,问所有人移动到房子里的最少花费. 其中,n,m<=100,最多有100个人. 最小给用流裸题. 建立一个超级源点,跟每一个房子连一条边,容量为1,花费为0 每一个人与超级汇点连一条边,容量为1,花费为0 一个房子与每一个人建一条边,房子指向人,容量为1,花费用2者的距离(不是直线距离) 然后跑最小费用流算

poj 2195 Going Home 二分图最小权匹配KM算法

题意: 有n个人要回到n间房子里,每间房子只允许一个人,求n个人要走的最小距离和. 分析: 裸的二分图最小权匹配,KM搞之. 代码: //poj 2195 //sep9 #include <iostream> using namespace std; const int maxN=128; char g[maxN][maxN]; int mx[maxN],my[maxN],hx[maxN],hy[maxN]; int w[maxN][maxN]; int lx[maxN],ly[maxN],l

POJ 3020 Antenna Placement ,二分图的最小路径覆盖

题目大意: 一个矩形中,有N个城市'*',现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市. 问至少放置多少个基站才能使得所有的城市都覆盖无线? 无向二分图的最小路径覆盖 = 顶点数 –  最大二分匹配数/2 路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联: #include<cstdio> #include<cstring> #include<vector> #include<algor

poj 2446 Chessboard (二分图利用奇偶性匹配)

Chessboard Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 13176   Accepted: 4118 Description Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2

二分图最优匹配模板

const int MAX = 1e6+10;const int inf = 0x3f3f3f3f;int n,m;int lx[MAX],ly[MAX];int match[MAX];int usex[MAX],usey[MAX];int w[MAX][MAX];int find(int u) {    usex[u]=1;    for(int i=0;i<m;i++) {        if(!usey[i]&&w[u][i]==ly[i]+lx[u]) {          

POJ 2195 Going Home / HDU 1533(最小费用最大流模板)

题目大意: 有一个最大是100 * 100 的网格图,上面有 s 个 房子和人,人每移动一个格子花费1的代价,求最小代价让所有的人都进入一个房子.每个房子只能进入一个人. 算法讨论: 注意是KM 和 MCMF算法,我写的是MCMF算法,一开始想的是连10000个点,但是不会连那些大众点之间的边,只会连超级点和普通点之间的边.后来觉得只要连房子点和 人点就可以了.连从人到房子的边,容量是1,花费是他们之间的曼哈顿距离,然后超级源点和超级汇点像上面那样连接,注意连点的时候把他们每个点都具体化一下,就

POJ 2195 Going Home (最小费用最大流)

题目链接:http://poj.org/problem?id=2195 题意:n*m的矩阵,地图上有若干个人(m)和房子(H),且人与房子的数量一致.man每移动一格费用为1,一个房子只能住一个人.现在要求所有的人出发,都入住房子,求最少话费. 思路:建立一个超级源点和汇点,源点与人相连费用为0,容量为1,人与房子相连,费用为人与房子的距离,容量为1,房子与汇点相连,费用为0,容量为1 #include <iostream> #include <cstdlib> #include

POJ 2536 Gopher II(二分图的最大匹配)

题目链接:http://poj.org/problem?id=2536 题意:已知有n只老鼠的坐标,m个洞的坐标,老鼠的移动速度为V,S秒以后有一只老鹰要吃老鼠,问有多少个老鼠被吃. 很明晰,二分匹配,老鼠为X集合,洞为Y集合 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <m

POJ 3686 The Windy&#39;s【最小权匹配(神建图啊)】

大意:有n个任务m个机器,告诉你n*m的矩阵表示每个任务在每个机器上完成需要的时间 问所有任务完成的总时间最少?(比如第一个任务在第一分钟完成第二个任务在第二分钟完成   则总时间为1 + 2 = 3 分析: 该题自己做的时候没有思路 后来在网上搜题解,感觉建图真是太厉害了 假设最优情况下,个个任务需要的时间分别为a1, a2, a3, ……,an 那么总时间t = n * a1 + (n - 1) * a2 + ……+ 2 * an - 1 + an 也就是说只需要考虑系数就可以了 我们先假设