LA4043 - Ants(二分图完备最佳匹配KM)

option=com_onlinejudge&Itemid=8&page=show_problem&problem=2044">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2044

大致题意:

平面上有n个白点和n个黑点,求一种完美匹配使他们间的连线不相交

思路:要注意到,若有两种匹配相交,总能够当成对角线补成四边形,然后选四边形的两个边作为匹配就不会相交,并且一定匹配后的距离和缩短了,简单的几何知识,显然最小权匹配不会出现相交情况

防止被卡精度用了龙龙

//	Accepted	C++11	0.079
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <ctime>
#include <bitset>
#include <algorithm>
#define SZ(x) ((int)(x).size())
#define ALL(v) (v).begin(), (v).end()
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define reveach(i, v) for (__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++ i)
#define REP(i,n) for ( int i=1; i<=int(n); i++ )
#define rep(i,n) for ( int i=0; i<int(n); i++ )
using namespace std;
typedef long long ll;
#define X first
#define Y second
typedef pair<ll,ll> pii;

template <class T>
inline bool RD(T &ret) {
    char c; int sgn;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && (c<'0' || c>'9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}
template <class T>
inline void PT(T x) {
    if (x < 0) {
        putchar('-');

        x = -x;
    }
    if (x > 9) pt(x / 10);
    putchar(x % 10 + '0');
}

const int N = 100+10;
const ll inf = 1LL<<50;
pii poix[N],poiy[N];
int n;
ll mp[N][N];

ll dis(int x,int y){
        ll a = poix[x].X-poiy[y].X, b = poix[x].Y-poiy[y].Y;
        return (a*a+b*b);
}

int link[N];
ll lx[N],ly[N]; //y中各点匹配状态,x,y中的点标号
ll sla[N];
bool visx[N],visy[N];
bool DFS(int x)
{
        visx[x] = true;
        REP(y,n){
                if(visy[y])continue;
                ll tmp = lx[x] + ly[y] - mp[x][y];
                if(tmp == 0){
                        visy[y] = true;
                        if(link[y] == -1 || DFS(link[y])){
                                link[y] = x;
                                return true;
                        }
                }
                else if(sla[y] > tmp) sla[y] = tmp;
        }
        return false;
}
ll KM()
{
        memset(link,-1,sizeof(link));
        memset(ly,0,sizeof(ly));
        REP(i,n){
                lx[i] = -inf;
                REP(j,n) lx[i] = max(lx[i],mp[i][j]);
        }
        REP(x,n){
                REP(i,n) sla[i] = inf;
                while(true)
                {
                        memset(visx,false,sizeof(visx));
                        memset(visy,false,sizeof(visy));
                        if(DFS(x)) break;
                        ll d = inf;
                        REP(i,n) if(!visy[i]) d = min(d,sla[i]);
                        REP(i,n){
                                if(visx[i]) lx[i] -= d;
                                if(visy[i])ly[i] += d;
                                else sla[i] -= d;
                        }
                }
        }
        ll res = 0;
        REP(i,n) if(link[i] != -1) res += mp[link[i]][i];
        return res;
}

int main(){
        bool flag = 0;
        while(~scanf("%d",&n)){
                if(flag) puts("");
                flag = 1;
                REP(i,n) RD(poix[i].X),RD(poix[i].Y);
                REP(i,n) RD(poiy[i].X),RD(poiy[i].Y);
                REP(x,n) REP(y,n) mp[y][x] = -sqrt(dis(x,y))*10000000;
                KM();
                REP(i,n) printf("%d\n",link[i]);
        }
        //Print a blank line between datasets.
}
时间: 07-15

LA4043 - Ants(二分图完备最佳匹配KM)的相关文章

hdu2255 奔小康赚大钱 二分图最佳匹配--KM算法

传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子.这可是一件大事,关系到人民的住房问题啊.村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子.另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(

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

ACM学习历程—POJ3565 Ants(最佳匹配KM算法)

Young naturalist Bill studies ants in school. His ants feed on plant-louses that live on apple trees. Each ant colony needs its own apple tree to feed itself. Bill has a map with coordinates of n ant colonies and n apple trees. He knows that ants tra

Regionals 2015 &gt;&gt; Asia - Tehran &gt;&gt; 7530 - Cafebazaar【二分图最佳匹配】【KM】【最大费用流】

Regionals 2015 >> Asia - Tehran >> 7530 - Cafebazaar 题目链接:7530 题目大意:一个公司有n个开发者,有m个APP可开发.其中一些开发者必选,一些APP必选.已知每个开发者开发每个APP的收益,求最大收益.(每个开发者最多开发一个APP,每个APP最多一个人开发) 题目思路: 解法一:二分图最佳匹配(KM算法) 增加一些虚开发者和虚app,非必要app可以被虚开发者开发,收益为0,反过来非必要开发者可以开发虚app,收益为0.

HDU_2255 二分图最佳完美匹配 KM匈牙利算法

一开始还没看懂这个算法,后来看了陶叔去年的PPT的实例演示才弄懂 用一个lx[]和ly[]来记录X和Y集合中点的权值,有个定理是 lx[i]+ly[j]==w[i][j](边权值) 则该点是最佳匹配,因为首先 那个不等式肯定要>=的,否则就不满足题意了,如果是>则可以去匹配更有价值的边或者把权值降下来让匹配边的潜力更大. 所以只有把握了这个条件,其他就是走一遍最大匹配数.以及up()函数用来在无法匹配的时候,进行其他点的权值降低(也可以说是增广路的搜索)来得到匹配. #include <

POJ3565 Ants【二分图最佳匹配】

题目链接: http://poj.org/problem?id=3565 题目大意: 在坐标系中有N只蚂蚁,N棵苹果树,给你蚂蚁和苹果树的坐标.让每只蚂蚁去一棵苹果树, 一棵苹果树对应一只蚂蚁.这样就有N条直线路线,问:怎样分配,才能使总路程和最小,且 N条线不相交. 思路: 用一个图来说明思路. 假设A.B为蚂蚁,C.D为苹果树.则存在两种匹配:第一种是AD.BC,第二种是AC.BD. 根据三角形不等式AD+BC < AC+BD,最后得到很重要的一个性质--满足总路程之和最小 的方案一定不相交

【网络流24题】No.18 分配问题 (二分图最佳匹配 费用流|KM)

[题意] 有 n 件工作要分配给 n 个人做.第 i 个人做第 j 件工作产生的效益为 cij . 试设计一个将n 件工作分配给 n 个人做的分配方案, 使产生的总效益最大. 输入文件示例input.txt52 2 2 1 22 3 1 2 42 0 1 1 12 3 4 3 33 2 1 2 1 输出文件示例output.txt514 [分析] 很裸的..二分图最大权匹配. 等一下可以打一下KM... 1 #include<cstdio> 2 #include<cstdlib>

HDU2255 奔小康赚大钱【二分图最佳匹配】

题目链接: http://acm.hdu.edu.cn/showproblem.php? pid=2255 题目大意: 村里要分房子. 有N家老百姓,刚好有N间房子.考虑到每家都要有房住,每家必须分配到一间房子且 仅仅能分配到一间房子.另外, 村长为了得到最大利益,让老百姓对房子进行估价. 比方有3件房子,一 家老百姓能够对第一间出10万,对第二间出2万,对第三间出4万.第二家老百姓能够对第一间出8万, 对第二家出3万,对第三间出5万.那么问题来了:怎么分配,才干使利益最大化. (村民房子不一定

POJ2195 Going Home【二分图最佳匹配】

题目链接: http://poj.org/problem?id=2195 题目大意: 在一个N*M的矩阵中,有M个人和M个房子,每个人要安排一个房子,每个房子只能安排一个人. 而每个人移动一步需要一美元.那么问题来了:求为每个人安排房子移动所需要的金钱最小值是多 少. 思路: 做一个二分图,一边为人,另一边为房子,如果把人和房子之间的距离作为边权的话,问题就变成 了求带权二分图最小权和的最佳匹配.这里我们为了方便计算,吧人和房子之间的距离的负值作为 边权,那么就变成了求带权二分图最大权和的最佳匹