UVA1411 Ants(带权二分图的最大完美匹配、zkw费用流)

作者:神秘网友 发布时间:2020-09-30 20:24:20

UVA1411 Ants(带权二分图的最大完美匹配、zkw费用流)

UVA1411 Ants(带权二分图的最大完美匹配、zkw费用流)

UVA1411 Ants(带权二分图的最大完美匹配、zkw费用流)

UVA1411 Ants(带权二分图的最大完美匹配、zkw费用流)

题解

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>

using namespace std;

const int N = 507, M = 200007;
const double DINF = 1010580540, eps = 1e-5;

int n, m;
int head[N], ver[M], nex[M], tot, edge[M];
double cost[M];
double dist[N];
int maxflow, maxcost;
int S, T;
bool vis[N];
int xa[N], xb[N], ya[N], yb[N];
int ax[N], bx[N], ay[N], by[N];
deque<int>q;
bool ins[N];
int cur[N];

void add(int x, int y, int z, double c, bool o = 1)
{
    ver[tot] = y;
    edge[tot] = z;
    cost[tot] = c;
    nex[tot] = head[x];
    head[x] = tot ++ ;
    if(o)add(y, x, 0, -c, 0);
}

double get_dist(int x, int y){
    return sqrt((double)(xa[x] - xb[y]) * (xa[x] - xb[y]) + (double)(ya[x] - yb[y]) * (ya[x] - yb[y]));
}

bool spfa()
{
    memset(ins, 0, sizeof ins);
    for(int i = S; i <= T; ++ i)
        dist[i] = DINF;
    q.push_front(T);
    dist[T] = 0;
    ins[T] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop_front();
        ins[x] = 0;
        for(int i= head[x]; ~i; i = nex[i]){
            int y = ver[i];
            if(edge[i ^ 1] && dist[y] - dist[x] + cost[i] > eps){
                dist[y] = dist[x] - cost[i];
                if(!ins[y]){
                    if(!q.empty() && dist[y] < dist[q.front()])q.push_front(y);
                    else q.push_back(y);
                    ins[y] = 1;
                }
            }
        }
    }
    return dist[S] != DINF;
}

int dfs(int x, int flow)
{
    vis[x] = 1;
    if(x == T || !flow)return flow;
    int used = 0;
    for(int i = cur[x]; ~i; i = nex[i])
    {
        cur[x] = i;
        int y = ver[i];
        if(dist[y] - dist[x] + cost[i] <= eps && !vis[y] && edge[i]){
            int fl = dfs(y, min(flow, edge[i]));
            if(fl){
                used += fl;
                flow -= fl;
                edge[i] -= fl;
                edge[i ^ 1] += fl;
                maxcost += fl *cost[i];
                if(!flow)break;
            }
        }
    }
    return used;
}

void zkwmcmf(){
    while(spfa()){
        vis[T] = 1;
        while(vis[T]){
            memcpy(cur, head, sizeof head);
            memset(vis, 0, sizeof vis);
            int fl = dfs(S, DINF);
            maxflow += fl;
        }
    }
}

double Calc(int x,int y)
{
    return sqrt((double)(ax[x]-bx[y])*(ax[x]-bx[y])+(double)(ay[x]-by[y])*(ay[x]-by[y]));
}

int main()
{
    while(scanf("%d", &n) != EOF){
        memset(head, -1, sizeof head);
        maxflow = maxcost = tot = 0;
        S = 0, T = 2 * n + 1;
        for(int i = 1; i <= n; ++ i)
            scanf("%d %d", &ax[i], &ay[i]);
        for(int i = 1; i <= n; ++i)
            scanf("%d %d", &bx[i], &by[i]);
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                add(i, j + n, 1, Calc(i, j));
            }
        }

        for(int i = 1; i <= n; ++ i)
            add(S, i, 1, 0);
        for(int i = 1; i <= n; ++ i)
            add(i + n, T, 1, 0);

        zkwmcmf();
        for(int i = 1; i <= n; ++ i)
        for(int j = head[i]; ~j; j = nex[j]){
            int y = ver[j];
            if(!edge[j]){
                printf("%d\n", y - n);
                break;
            }
        }
    }
    return 0;
}

UVA1411 Ants(带权二分图的最大完美匹配、zkw费用流)相关教程

  1. hdu(3047)——Zjnu Stadium带权并查集

    hdu(3047)——Zjnu Stadium带权并查集 hdu(3047)——Zjnu Stadium hdu(3047)——Zjnu Stadium 题目传送门 题意:输入A、B、X 表示B要坐在A大X的座位,由于体育馆的行数可以视为无穷大,所以可以不考虑环形的循环,有n个人,m条数据,要求输出错误数据的条数。

  2. How Many Answers Are Wrong HDU - 3038(带权并查集)

    How Many Answers Are Wrong HDU - 3038(带权并查集) 题意: TT写一个数列,现在TT会选择一个区间,然后让FF计算这个区间里面所有数的和,FF准备捉弄一下TT,有时候她会故意计算出来一个错的答案,当然TT也比较聪明,他会发现这个答案跟以前的答案会有冲突

  3. 2020-09-14

    2020-09-14 单源无向带权图 求最短路径问题 问题描述: 给定一个起点 s 和一个终点 e , 从s 到 e 的路线有很多 , 每个顶点间的花费都有 代价 cost。 求从 s 能够到达 e 的路径花费的最少代价 。 大致图像百度的一个: Input : 输入格式: 第一行 m,n ,其中

  4. G. Path Queries(带权并查集+kruskal思想)

    G. Path Queries(带权并查集+kruskal思想) https://codeforces.com/problemset/problem/1213/G 题目描述 \mathsf E \color{red}\mathsf{ntropyIncreaser}EntropyIncreaser有一棵nn个点的树,每条边都带权。 她会问你mm个问题,每次给你一个正整数qq,求最大权

  5. 杭电3038——带权并差集

    杭电3038——带权并差集 杭电3038——带权并差集 原题传送门,带权并差集基本讲解。 写在题前: 这个题属于简单的带权并差集应用吧,稍微想想还是能想出来的。不过要注意并差集在建立关系时的边界问题: a:1 3 20 b:8 10 30 如果输入4 5 10 就需要和a数据建

  6. LintCode天梯(USGiants)-Integer Array

    LintCode天梯(USGiants)-Integer Array 喵,小喵爬天梯系列~美国大公司。 第二弹:整数数组。 题意: 给定一个数组和一个值,在原地删除与值相同的数字,返回新数组的长度。 元素的顺序可以改变,并且对新的数组不会有影响。 分析: 小喵的第一想法,竟然题目

  7. 赫夫曼编码

    赫夫曼编码 //赫夫曼编码:最优二叉树,是带权路径长度最短的二叉树; 根据结点的个数和权值不同,最优二叉树的形状也不同 //将每个带有权值的结点作为一颗仅有根结点 的二叉树,树的权值为节点的权值 //将其中两颗权值最小 的树组成一颗新二叉树,新树的权值

  8. 3.1 Introduction to determinants 行列式介绍

    3.1 Introduction to determinants 行列式介绍 本文为《Linear algebra and its applications》的读书笔记 目录 Definition Recall from Section 2.2 that a 2 2 2 \times 2 2 2 matrix is invertible if and only if its determinant is nonzero. To extend