2 条题解
-
0
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]={y,f,c,last[x]};last[x]=alen; a[++alen]={x,0,-c,last[y]};last[y]=alen; } int n,st,ed,match[N];int X[N],Y[N],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],inqueue[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;inqueue[st]=1; while(l!=r) { int x=q[l++];if(l==N)l=0;inqueue[x]=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(!inqueue[y]){inqueue[y]=1;q[r++]=y;if(r==N)r=0;} } } } return d[ed]<1e18; } 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=n+1;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<=2*n;j++)ins(i,j,1,get_dist(i,j)); dinic();for(int i=1;i<=2*n;i++)if(match[i])printf("%d\n",match[i]-n); return 0;} -
0
huangzheng
LV 6
@ 2025-10-8 16:57:07
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; }
- 1
