# 57 条题解

• @ 2017-09-04 19:32:18
``````#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>

#define INF 1000000007

using namespace std;

const int Maxn = 101010;

struct node {
int next, to, cap; double c;
} e[Maxn];

int xx1[Maxn], xx2[Maxn], yy1[Maxn], yy2[Maxn], n, S = 0, T, tot = 1, h[Maxn], pre[Maxn];
double dis[Maxn];
bool vis[Maxn];

double Dis(int x, int y) {
//  cout << xx1[x] << ' ' << xx2[y] << endl;
return sqrt((xx1[x] - xx2[y]) * (xx1[x] - xx2[y]) + (yy1[x] - yy2[y]) * (yy1[x] - yy2[y]));
}

void Link(int x, int y, int p, double c) {e[++tot] = (node){h[x], y, p, c}; h[x] = tot;}

void Add(int x, int y, int p, double c) {Link(x, y, p, c); Link(y, x, 0, -c);}

int Bfs() {
queue <int> Q;
for(int i = S; i <= T; ++i) dis[i] = 1e15, vis[i] = 0, pre[i] = 0;
Q.push(S); dis[S] = 0; vis[S] = 1;
while(!Q.empty()) {
int u = Q.front(); Q.pop(); vis[u] = 0;
//      cout << u << endl;
for(int i = h[u]; i; i = e[i].next) {
int v = e[i].to;
if(e[i].cap && dis[v] > dis[u] + e[i].c) {
pre[v] = i; dis[v] = dis[u] + e[i].c;
if(!vis[v]) {
vis[v] = 1;
Q.push(v);
}
}
}
}
return (dis[T] != 1e15);
}

double Mcmf() {
double ans = 0;
while(Bfs()) {
//      cout << '!';
int s = INF;
for(int i = pre[T]; i; i = pre[e[i ^ 1].to]) {
s = min(s, e[i].cap);
}
for(int i = pre[T]; i; i = pre[e[i ^ 1].to]) e[i].cap -= s, e[i ^ 1].cap += s;
ans += (double)s * dis[T];
}
return ans;
}

int main() {
scanf("%d", &n); T = 2 * n + 1;
for(int i = 1; i <= n; ++i) scanf("%d%d", &xx1[i], &yy1[i]);
for(int i = 1; i <= n; ++i) scanf("%d%d", &xx2[i], &yy2[i]);
//  cout << xx1[1] << ' ' << xx2[1] << endl;
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) {
//          cout << Dis(i, j) << endl;
Add(i, j + n, 1, Dis(i, j));
}
}
printf("%.3lf\n", Mcmf());
return 0;
}
``````
• @ 2017-07-17 15:23:43
``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n;
vector<int> e;
vector<int> pre;
vector<int> vis;
vector<vector<int> > cw;
vector<vector<int> > ce;
vector<double> f;
vector<double> u;
vector<double> m_x;
vector<double> m_y;
vector<double> t_x;
vector<double> t_y;
vector<vector<double> > c;
vector<vector<double> > p;
deque<int> q;

void add_edge_1(int x,int y,double c_v,double p_v)
{
cw[x].push_back(y);
c[x].push_back(c_v);
p[x].push_back(p_v);
ce[y].push_back(cw[x].size()-1);
cw[y].push_back(x);
c[y].push_back(0);
p[y].push_back(-p_v);
ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,double *flow,double *cost)
{
f.resize(0);
f.resize(cw.size(),0);
f[s]=oo_max;
e.resize(0);
e.resize(cw.size(),-1);
u.resize(0);
u.resize(cw.size(),oo_max);
u[s]=0;
pre.resize(0);
pre.resize(cw.size(),-1);
pre[s]=s;
vis.resize(0);
vis.resize(cw.size(),0);
for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
{
int now=q.front();
for (int i=0;i<cw[now].size();i++)
if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
{
f[cw[now][i]]=min(c[now][i],f[now]);
e[cw[now][i]]=i;
u[cw[now][i]]=u[now]+p[now][i];
pre[cw[now][i]]=now;
if (vis[cw[now][i]]==0)
vis[cw[now][i]]=1,q.push_back(cw[now][i]);
}
}
(*flow)=f[t];
(*cost)=u[t];
return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,double *flow,double *cost)
{
double temp_flow,temp_cost;
while (bfs_1(s,t,&temp_flow,&temp_cost))
{
for (int i=t;i!=s;i=pre[i])
c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
(*flow)+=temp_flow;
(*cost)+=temp_cost;
}
}

int main()
{
while (~scanf("%d",&n))
{
cw.resize(0);
cw.resize(2*n+2);
ce.resize(0);
ce.resize(cw.size());
c.resize(0);
c.resize(cw.size());
p.resize(0);
p.resize(cw.size());
for (int i=0;i<cw.size();i++)
{
cw[i].resize(0);
ce[i].resize(0);
c[i].resize(0);
p[i].resize(0);
}
m_x.resize(0);
m_x.resize(n+1,0);
m_y.resize(0);
m_y.resize(n+1,0);
for (int i=1;i<=n;i++)
{
scanf("%lf%lf",&m_x[i],&m_y[i]);
}
t_x.resize(0);
t_x.resize(n+1,0);
t_y.resize(0);
t_y.resize(n+1,0);
for (int i=1;i<=n;i++)
{
scanf("%lf%lf",&t_x[i],&t_y[i]);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
double ans_flow=0,ans_cost=0;
min_cost_max_flow_1(0,c.size()-1,&ans_flow,&ans_cost);
printf("%.3lf\n",ans_cost);
}
}
``````
• @ 2017-07-17 15:24:02

很H2O的题

• @ 2016-06-07 20:52:01

网络流可能会好一些，不过集合dp也是可以秒杀的。
```c++
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1<<20;
double const fix = 1e-6;

struct Po
{
int x,y;
Po(int a=0,int b=0) : x(a),y(b) {}
};

double pro_dis(const Po &a,const Po &b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

Po missiles[30],target[30];
double info[maxn];
int n;

inline int bitcount(int a)
{
return a==0 ? 0 : bitcount(a>>1)+(a&1);
}

double dp(int S)
{
if(info[S]>=0) return info[S];
int m = bitcount(S);
Po now=missiles[m];
for(int i=0;i<n;i++)
if(S&(1<<i))
{
if(info[S]<0) info[S]= pro_dis(target[i+1],now) + dp(S^(1<<i));
else info[S] = min(info[S],pro_dis(target[i+1],now) + dp(S^(1<<i)));
}
return info[S];
}

int main()
{
scanf("%d",&n);
info[0]=0;
for(int i=1;i<(1<<n);i++)
info[i]=-1.0;
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
missiles[i]=Po(a,b);
}
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
target[i]=Po(a,b);
}

double ans = dp((1<<n)-1);
printf("%.3lf\n",ans);
return 0;
}
```

• @ 2015-11-14 23:04:30

最小费用最大流 0 ms
对于任意一个导弹，将其与所有目标连边（即每个导弹连 n 条边），费用=两点距离，容量=1
然后加一个源点（指向所有导弹）与一个汇点（所有目标指向它），这些边费用都为0，容量都为1
然后开始网络流...

• @ 2015-02-04 12:24:46

浮点数的最小费用流写得疼死了....

##Code

db INF=1e20;
db eps=1e-11;
bool fequal(db a,db b)
{ return fabs(a-b)<eps; }

//maxflow

struct edge
{
int in;
int c;
db v;
edge*nxt;
edge*ptr;
}pool[100000];
edge*et=pool;
edge*eds[1000];
void addedge(int i,int j,int c,db v)
{
et->ptr=et+1;
et->in=j; et->c=c; et->v=v; et->nxt=eds[i]; eds[i]=et++;
et->ptr=et-1;
et->in=i; et->c=0; et->v=-v; et->nxt=eds[j]; eds[j]=et++;
}
#define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)

int n;
int st,ed;

db cost;
db dist[1000];
bool used[1000];
int DFS(int x,int mi)
{
if(x==ed) return mi;
used[x]=true;
int res=0; int c;
FOREACH_EDGE(i,x)
if(i->c>0 && !used[i->in] && fequal(dist[x]+i->v,dist[i->in]) && ( c=DFS(i->in,min(i->c,mi)) ))
{
res+=c;
i->c-=c;
i->ptr->c+=c;
mi-=c;
cost+=db(c)*i->v;
if(mi==0) break;
}
used[x]=false;
if(res==0) dist[x]=INF;
return res;
}

int qh,qt;
int q[4000000];
db DINIC()
{
db res=0.0;

while(true)
{
fillarray(dist,INF,n);
qh=qt=0;
q[qt++]=st;
dist[st]=0;
while(qh!=qt)
{
int&cur=q[qh];
FOREACH_EDGE(i,cur)
if( i->c>0 && dist[i->in] > dist[cur] + i->v )
{
dist[i->in]=dist[cur]+i->v;
q[qt++]=i->in;
}
qh++;
}

if(dist[ed]>=INF) break;

cost=0;
if(0==DFS(st,(1<<28)-1)) break;
res+=cost;
}

return res;
}

//=================================================

int ptot;
int mx[1050];
int my[1050];
int ex[1050];
int ey[1050];

db dst(int i,int j)
{ return sqrt(db(mx[i]-ex[j])*db(mx[i]-ex[j])+db(my[i]-ey[j])*db(my[i]-ey[j])); }

//blocks define
#define MISSILE(i) (i)
#define ENEMY(i) ((i)+ptot)

int main()
{
ptot=getint();
for(int i=0;i<ptot;i++)
mx[i]=getint(),my[i]=getint();
for(int i=0;i<ptot;i++)
ex[i]=getint(),ey[i]=getint();

st=ptot*2;
ed=st+1;
n=ed+1;

for(int i=0;i<ptot;i++)
for(int j=0;j<ptot;j++)

for(int i=0;i<ptot;i++)

for(int i=0;i<ptot;i++)

printf("%.3lf\n",DINIC());

return 0;
}

• @ 2019-04-02 16:50:05

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

#define INF 1000000007

using namespace std;

const int Maxn = 101010;

struct node {
int next, to, cap; double c;
} e[Maxn];

int xx1[Maxn], xx2[Maxn], yy1[Maxn], yy2[Maxn], n, S = 0, T, tot = 1, h[Maxn], pre[Maxn];
double dis[Maxn];
bool vis[Maxn];

double Dis(int x, int y) {
// cout << xx1[x] << ' ' << xx2[y] << endl;
return sqrt((xx1[x] - xx2[y]) * (xx1[x] - xx2[y]) + (yy1[x] - yy2[y]) * (yy1[x] - yy2[y]));
}

void Link(int x, int y, int p, double c) {e[++tot] = (node){h[x], y, p, c}; h[x] = tot;}

void Add(int x, int y, int p, double c) {Link(x, y, p, c); Link(y, x, 0, -c);}

int Bfs() {
queue <int> Q;
for(int i = S; i <= T; ++i) dis[i] = 1e15, vis[i] = 0, pre[i] = 0;
Q.push(S); dis[S] = 0; vis[S] = 1;
while(!Q.empty()) {
int u = Q.front(); Q.pop(); vis[u] = 0;
// cout << u << endl;
for(int i = h[u]; i; i = e[i].next) {
int v = e[i].to;
if(e[i].cap && dis[v] > dis[u] + e[i].c) {
pre[v] = i; dis[v] = dis[u] + e[i].c;
if(!vis[v]) {
vis[v] = 1;
Q.push(v);
}
}
}
}
return (dis[T] != 1e15);
}

double Mcmf() {
double ans = 0;
while(Bfs()) {
// cout << '!';
int s = INF;
for(int i = pre[T]; i; i = pre[e[i ^ 1].to]) {
s = min(s, e[i].cap);
}
for(int i = pre[T]; i; i = pre[e[i ^ 1].to]) e[i].cap -= s, e[i ^ 1].cap += s;
ans += (double)s * dis[T];
}
return ans;
}

int main() {
scanf("%d", &n); T = 2 * n + 1;
for(int i = 1; i <= n; ++i) scanf("%d%d", &xx1[i], &yy1[i]);
for(int i = 1; i <= n; ++i) scanf("%d%d", &xx2[i], &yy2[i]);
// cout << xx1[1] << ' ' << xx2[1] << endl;
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) {
// cout << Dis(i, j) << endl;
Add(i, j + n, 1, Dis(i, j));
}
}
printf("%.3lf\n", Mcmf());
return 0;
}

• @ 2016-10-23 14:53:20

二分图最大权匹配,用KM算法即可。
没看到“使每个导弹到其目标的距离之和最小。”，一直求最大。。。。对这个，只要取负数最后反转即可。

``````//KM
#include<cstdio>
#include<cstring>
#include<cmath>
#define eps 1e-5
const int INF=0x3f3f3f3f;
using namespace std;
int n;
double w[22][22],lx[22],ly[22],lack;
bool visx[22],visy[22];
struct point{
int x,y;
}p[22];
bool dfs(int x){
visx[x]=1;
for(int y=1;y<=n;y++)
if(!visy[y]){
double t=lx[x]+ly[y]-w[x][y];
if(t<eps){
visy[y]=1;
return 1;
}
}else if(lack-eps>t)lack=t;
}
return 0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
for(int i=1;i<=n;i++){
int X,Y;
scanf("%d%d",&X,&Y);
for(int j=1;j<=n;j++)
w[i][j]=-sqrt( pow(p[j].x-X,2.0)+pow(p[j].y-Y,2.0) );
}
for(int i=1;i<=n;i++)ly[i]=0.000;
for(int i=1;i<=n;i++){
lx[i]=INF;
for(int j=1;j<=n;j++)
if(w[i][j]-eps>lx[i])lx[i]=w[i][j];
}
for(int x=1;x<=n;x++){
for(;;){
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
lack=INF;
if(dfs(x))break;
for(int i=1;i<=n;i++){
if(visx[i])lx[i]-=lack;
if(visy[i])ly[i]+=lack;
}
}
}
double res=0.000;
for(int i=1;i<=n;i++)
printf("%.3f\n",res);
return 0;
}
``````
• @ 2014-09-07 17:14:02

题目略坑。。

• @ 2014-07-08 10:29:00

注意不能d=0，显然会t解

• @ 2010-03-05 21:49:57

20*20的KM？

• @ 2009-11-06 20:22:43

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

终于A了，，膜拜K-Boy巨快如闪电。。。

• @ 2009-11-01 14:13:33

我写出来的精度有问题．．

先把费用乘一个10e5 算出结果后再除 才过了的

用int64记录

• @ 2009-10-13 18:04:10

预处理出所有不相交的直线，然后再搜索，会发现速度巨快如闪电....

另：最优化也是要加的........

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-09-15 21:39:58
• @ 2009-09-12 19:31:47

费用流（spfa的）和km都没有精度的问题，都是0ms。各写了一遍。

• @ 2009-09-06 11:15:51

极其郁闷..

把for i:=1 to n do for j:=1 to n do

改成 for i:=1 to n do for j:=n downto 1 do

就过了...

纪念300题

• @ 2009-07-30 14:08:41

先随便弄一个匹配，然后调整。如果x1到y1的距离+x2到y2的距离>x1到y2的距离+x2到y1的距离就交换。

但是一直90。抓狂。浪费我一大堆提交。

结果看了这页的题解发现，初始时不要贪心着弄匹配，直接第i个跟第i个相连就行了。还有，for i:=1 to n do for j:=n downto 1 do就Ac了

大概这个方法不对吧？是拼RP的吧？不清楚，汗……

• @ 2009-07-23 09:43:01

第一次写费用流。。。。

• @ 2009-07-21 18:09:29

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

费用流随便写写。。。

• @ 2009-04-05 15:36:00

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

ID
1228

7

(无)

710

151

21%

4