感谢溪桥、吾愿提供另一种思路

再次感谢Jimmy.Carlson.Wang带我翻译题目

这一题除了上次瞎搞以外,还可以写网络流算法

或者说..最小费用最大流..

考虑任意一个苹果树和蚂蚁连一条距离为1,费用为dist(x,y)的边

s向苹果树连一条距离为1,费用为0的边;蚂蚁向t连一条距离为1,费用为0的边

这样建图跑一次可以保证总距离最小

总距离最小的话,不会有交叉(不然将它们换过来会更小)

所以..算法得证明正确性

*spfa写错了gg....调了半天

论正确写spfa的重要性....

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf=99999999;
int x[205],y[205];
double dists(int x,int y)
{
    return sqrt((double)(x*x+y*y));
}
struct edge
{
    int y;
    int weight;
    double cost;
    edge * next;
    edge * anti;
};
edge * li[205];
edge * new_edge()
{
    static edge a[100005];
    static int top=0;
    return &a[top++];
}
edge * inserts(int x,int y,int z,double w)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->cost=w;
    t->next=li[x];
    li[x]=t;
    return t;
}
void insert_edge(int x,int y,int z,double w)
{
    edge * t1=inserts(x,y,z,w);
    edge * t2=inserts(y,x,0,-w);
    t1->anti=t2;
    t2->anti=t1;
}
double dist[1005];
bool visit[205];
int pre[205];
edge * path[205];
const double eps=1e-5;
double spfa(int s,int t)
{
    int i;
    for (i=0;i<205;i++)
    {
        dist[i]=inf;
    }
    dist[s]=0;
    memset(pre,-1,sizeof(pre));
    memset(path,0,sizeof(path));
    static int que[405];
    int front=0,rail=1;
    que[0]=s;
    memset(visit,0,sizeof(visit));
    visit[s]=true;
    for (;front!=rail;)
    {
        int now=que[front];
        front++;
        if (front==404) front=0;
        edge * x;
        for (x=li[now];x!=0;x=x->next)
        {
            if ((x->weight>0)&&(dist[now]+x->cost+eps<dist[x->y]))
            {
                dist[x->y]=dist[now]+x->cost;
                pre[x->y]=now;
                path[x->y]=x;
                if (!visit[x->y])
                {
                    visit[x->y]=true;
                    que[rail++]=x->y;
                    if (rail==404) rail=0;
                }
            }
        }
        visit[now]=false;
    }
    return dist[t];
}
void max_flow_min_cost(int s,int t)
{
    for (;spfa(s,t)!=inf;)
    {
        int now=t;
        int mins=inf;
        for (;now!=s;now=pre[now])
        {
            mins=min(mins,path[now]->weight);
        }
        now=t;
        for (;now!=s;now=pre[now])
        {
            path[now]->weight-=mins;
            path[now]->anti->weight+=mins;
        }
    }
}
int main()
{
    freopen("ants.in","r",stdin);
    freopen("ants.out","w",stdout);
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n+n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    int s=n+n,t=n+n+1;
    for (i=0;i<n;i++)
    {
        insert_edge(s,i,1,0);
    }
    for (i=0;i<n;i++)
    {
        int j;
        for (j=n;j<n+n;j++)
        {
            insert_edge(i,j,1,dists(x[i]-x[j],y[i]-y[j]));
        }
    }
    for (i=0;i<n;i++)
    {
        insert_edge(i+n,t,1,0);
    }
    max_flow_min_cost(s,t);
    for (i=0;i<n;i++)
    {
        edge * t;
        for (t=li[i];t!=0;t=t->next)
        {
            if (t->weight==0)
            {
                printf("%d\n",t->y-n+1);
            }
        }
    }
    return 0;
}