题目描述

平面上共有2*N个点，N个是白点，N个是黑点。
对于每个白点，找到一个黑点，把二者用线连起来，要求最后所有线段都不相交，求一种方案。
输入格式
第一行包含整数N。
接下来N行，每行两个整数，表示一个黑点的坐标。
再接下来N行，每行两个整数，表示一个白点的坐标。
输出格式
输出共N行，每行一个整数。
第 i 行的数，表示第 i 个黑点连接的白点的编号，编号从1开始。
注意答案可能不唯一，任意输出一种答案即可。
数据范围
1≤N≤100
1≤N≤100
,坐标绝对值不超过10000。

样例

blablabla

算法1

算法 : 最小费用流

有N个黑点, N个白点,黑点和白点连线 ,没有交叉的线段 , 那么对应的线段长度和一定最小,反之对应的线段和最小,一定没有交叉的线段

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-8;
const int N = 510 , M = 1e6 + 4 * N + 110;

struct Point{
    double x,y;
}white[N],black[N];

int n, S , T;
bool st[N];
int q[N];
int h[2 * N],e[M] , ne[M] ,f[M] ,idx;
int incf[N], pre[N] , max_flow ,res[N];
double d[N], ans ,w[M];

double get_dist(Point& p ,Point& q)
{
    double dx = p.x - q.x;
    double dy = p.y - q.y;
    return sqrt(dx * dx + dy * dy);
}

void  add(int a,int b,int c , double cost)
{
    e[idx] = b , ne[idx] = h[a] , f[idx] = c , w[idx] = cost , h[a] = idx++;
    e[idx] = a , ne[idx] = h[b] , f[idx] = 0 , w[idx] = -cost , h[b] = idx++;
}

int dcmp(double x) {
    if(fabs(x)<eps)return 0;
    else return x<0?-1:1;
}

bool spfa()
{
    int hh = 0, tt = 1;
    for(int i = 0 ; i <= 2 * n + 1 ; i++)d[i] = 949494999944;
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = 0x3f3f3f3f;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N ) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (f[i] && 0 > dcmp(d[t] + w[i] - d[ver] ))
            {
                d[ver] = d[t] + w[i];
                pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if (!st[ver])
                {
                    q[tt ++ ] = ver;
                    if (tt == N ) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}




void EK(){

    while(spfa())
    {
       //cout << 1 << endl;
        for(int i = T ; i != S ; i = e[pre[i] ^ 1])
            f[pre[i]] -= incf[T] , f[pre[i] ^ 1] += incf[T];

        max_flow += incf[T];
        ans += d[T] ;
    }

}


int main(){

    cin >> n;
    S = 0, T = 2 * n + 1;
    for(int i = 1 ; i <= n ; i++)cin >> black[i].x >> black[i].y;

    for(int i = 1 ; i <= n ; i++)cin >> white[i].x >> white[i].y;

    memset(h , -1 , sizeof h);
    for(int i = 1 ; i <= n ; i++)
    {
        add(S , i , 1 , 0);
        add(i + n ,T ,  1 , 0);
    }

    for(int i = 1 ; i <= n ; i++)
       for(int j = 1 ; j <= n ; j++)
          add(i , j + n , 1 , get_dist(white[i] , black[j]));


       // cout << get_dist(white[1] , black[1]) << endl;  
    EK();      
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = h[i] ; ~j ; j = ne[j])
           if(f[j] == 0){
               res[e[j] - n] = i;
               break;
           }
           //cout << endl;
    }

    for(int i = 1 ; i <= n ; i++)cout << res[i] << endl;
    return 0;
}