*【二分图：带权最大匹配】蚂蚁
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
【题意】0x60图论（0x68 二分图的匹配）例题5：蚂蚁（负责人：陈煜）平面上共有2*N个点，N个是白点，N个是黑点。
对于每个白点，找到一个黑点，把二者用线连起来，要求最后所有线段都不相交，求一种方案。
【输入格式】
第一行包含整数N。
接下来N行，每行两个整数，表示一个黑点的坐标。
再接下来N行，每行两个整数，表示一个白点的坐标。
【输出格式】
输出共N行，每行一个整数。
第 i 行的数，表示第 i 个黑点连接的白点的编号，编号从1开始。
注意答案可能不唯一，任意输出一种答案即可。
【数据范围】
1≤N≤100,坐标绝对值不超过10000。
【输出样例】
5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60
【输出样例】
4
2
1
5
3
（本题正式开放SPJ）
Hint
KM算法：#include<bits/stdc++.h>
using namespace std;
int n,match[110],va[110],vb[110];double la[110],lb[110],upd[110],w[110][110];
struct node{double x,y;}a[110],b[110];
double dis(node a,node b){double x=abs(a.x-b.x),y=abs(a.y-b.y);return sqrt(x*x+y*y);}
bool dfs(int x)
{
va[x]=1;
for(int y=1;y<=n;y++)if(!vb[y])
{
if(abs(la[x]+lb[y]-w[x][y])<1e-9)
{
vb[y]=1;
if(!match[y]||dfs(match[y]))
{
match[y]=x;
return 1;
}
}
else upd[y]=min(upd[y],la[x]+lb[y]-w[x][y]);
}
return 0;
}
void KM()
{
for(int i=1;i<=n;i++)
{
la[i]=-1e9;for(int j=1;j<=n;j++)la[i]=max(la[i],w[i][j]);
lb[i]=0;
}
for(int i=1;i<=n;i++)
{
while(1)
{
for(int j=1;j<=n;j++)va[j]=vb[j]=0,upd[j]=1e9;
if(dfs(i))break;
double delta=1e9;for(int j=1;j<=n;j++)if(!vb[j])delta=min(delta,upd[j]);
for(int j=1;j<=n;j++)
{
if(va[j])la[j]-=delta;
if(vb[j])lb[j]+=delta;
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&b[i].x,&b[i].y);
for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)w[i][j]=-dis(a[i],b[j]);
KM();
for(int i=1;i<=n;i++)printf("%d\n",match[i]);
return 0;
}
费用流：
#include<bits/stdc++.h>
using namespace std;
const int N=505,M=1e5+5;
const int inf=0x3f3f3f3f;
struct edge{int y,f;double c;int pre;}a[M<<1];int alen=1,last[N];
void ins(int x,int y,int f,double c)
{
a[++alen]=edge{y,f,c,last[x]};last[x]=alen;
a[++alen]=edge{x,0,-c,last[y]};last[y]=alen;
}
int n,st,ed,match[N];
int X[N],Y[N];
int cur[N];
double get_dist(int i,int j){return sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));}
double d[N];
bool v[N];
int q[N];
bool spfa()
{
for(int i=0;i<=ed;i++)d[i]=1e18;
memset(v,0,sizeof(v));
memcpy(cur,last,sizeof(cur));
d[st]=0;
int l=0,r=0;
q[r++]=st;
while(l!=r)
{
int x=q[l++];if(l==N)l=0;
for(int k=last[x];k;k=a[k].pre)
{
int y=a[k].y;
if(a[k].f&&d[y]>d[x]+a[k].c)
{
d[y]=d[x]+a[k].c;
if(!v[y])
{
v[y]=1;
q[r++]=y;
if(r==N)r=0;
}
}
}
v[x]=0;
}
return d[ed]<d[0];
}
int findflow(int x,int f)
{
v[x]=1;
if(x==ed)return f;
int sx=0;
for(int k=cur[x];k;k=a[k].pre)
{
cur[x]=k;
int y=a[k].y;
if(a[k].f&&!v[y]&&d[y]>=d[x]+a[k].c)
{
int sy=findflow(y,min(a[k].f,f-sx));
a[k].f-=sy;a[k^1].f+=sy;sx+=sy;
if(!a[k].f)match[x]=y;
if(sx==f)return sx;
}
}
v[x]=0;
return sx;
}
int dinic()
{
int s=0;
while(spfa())s+=findflow(st,inf);
return s;
}
int main()
{
scanf("%d",&n);
st=n*2+1;ed=st+1;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&X[i],&Y[i]);
ins(st,i,1,0);
}
for(int i=1+n;i<=2*n;i++)
{
scanf("%d%d",&X[i],&Y[i]);
ins(i,ed,1,0);
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=n*2;j++)
ins(i,j,1,get_dist(i,j));
dinic();
for(int i=1;i<=n;i++)
printf("%d\n",match[i]-n);
return 0;
}