[文章目录]
Description
现在我们有N（N<=20）个导弹。需要在最短的时间内，用这N个导弹摧毁敌方N个目标(1个导弹只能摧毁1个目标)。给出每个导弹的降落位置和目标的位置，请你编程帮助给每个导弹确定目标，使每个导弹到其目标的距离之和最小
建立一张图，s向每个导弹连边，每个目标向t连边，边权都为1。费用为0，使得跑出来的最大流就是n，（即每个导弹都打了一个目标）。然后n个导弹向n个目标连边，边权一定要为1（在vijos inf居然过了，ss啦！！！）【因为如果边权为inf时会造出一个反向弧，然后就形成了一个费用为零的环】，费用为两点间的距离。然后跑一边最小费用最大流就好了。
然后，看一下最小费用最大流算法。
不是说有一个EK吗，所以关键的最小费用就是在点的决定遍历顺序上，用spfa跑出一条最小费用路径，然后记录路径，增广。ans加上费用。（利用贪心思想可知费用一定是最小的）
另外由于后向弧的撤销作用，反向弧的费用需要为正向弧费用的相反数（跑了后向弧时减去一开始加上的费用）。
还有 double类型不能清成0x3f，并不是最大值。手动吧。
基本的最小费用都是在流量上有一个单价，所以需要乘一个流量（然而这题并不需要）。
代码细节比较多。需要理解。
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int x[50],y[50],gx[50],gy[50],n,s,t;
int head[50],path[50],to[1000],nxt[1000],f[1000],cnt=1,inf=0x3f3f3f3f;
double val[1000];
queue<int> q;
double Dis(int x,int y,int dx,int dy)
{
return sqrt((x-dx)*(x-dx)+(y-dy)*(y-dy));
}
void add(int x,int y,int z,double w)
{
to[++cnt]=y;
nxt[cnt]=head[x];
f[cnt]=z;
val[cnt]=w;
head[x]=cnt;
to[++cnt]=x;
nxt[cnt]=head[y];
f[cnt]=0;
val[cnt]=-w;//反向弧的费用为负
head[y]=cnt;
}
double dis[50];//原来bfs分层的依据更新成了费用最短路
bool v[50];//spfa
bool spfa()
{
for(int i=(n<<1)+2;i;i--) dis[i]=inf,v[i]=0;
while(!q.empty()) q.pop();
q.push(s);dis[s]=0;v[s]=1;
while(!q.empty())
{
int x=q.front();q.pop();
v[x]=false;
for(int y,i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[y=to[i]]>dis[x]+val[i])
{
dis[y]=dis[x]+val[i];
path[y]=i^1;//path[i]记录的是到某个点的边的反向边的编号，用来从汇点找回路径
if(!v[y]) q.push(y),v[y]=1;
}
}
return dis[t]<inf;
}
double mincost()
{
double ans=0;
while(spfa())
{
int minflow=1<<30;
for(int i=t;i!=s;i=to[path[i]]) minflow=min(minflow,f[path[i]^1]);
for(int i=t;i!=s;i=to[path[i]])
{
f[path[i]]+=minflow;
f[path[i]^1]-=minflow;
ans+=val[path[i]^1]*minflow;//单价*流量
}
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++) scanf("%d%d",&gx[i],&gy[i]);
s=(n<<1)+1;
t=(n<<1)+2;
for(int i=1;i<=n;i++)
{
add(s,i,1,0);
add(i+n,t,1,0);
for(int j=1;j<=n;j++)
add(i,n+j,1,Dis(x[i],y[i],gx[j],gy[j]));
}
printf("%.3lf\n",mincost());
return 0;
}