原题传送门 https://www.luogu.org/problemnew/show/UVA1411
博客里对二分图匹配的详细介绍
这道题是带权二分图匹配
用的是 KM 算法
我们要知道一个定理: 要使线段没有相交, 要使距离总和最小
我们先把任意一对白点, 黑点的距离算一下
然后运用 KM 算法
因为要最小权值, 所以需要把权值取反来求最大.
- #include <bits/stdc++.h>
- #define N 105
- using namespace std;
- inline void write(register int x)
- {
- if(!x)putchar('0');if(x<0)x=-x,putchar('-');
- static int sta[25];int tot=0;
- while(x)sta[tot++]=x%10,x/=10;
- while(tot)putchar(sta[--tot]+48);
- }
- inline double Max(register double x,register double y)
- {
- return x>y?x:y;
- }
- inline double Min(register double x,register double y)
- {
- return x<y?x:y;
- }
- int n;
- double X1[N],Y1[N],X2[N],Y2[N];
- double dis[N][N];
- double lx[N],ly[N];
- int link[N],s[N],t[N];
- inline bool dfs(register int x)
- {
- s[x]=1;
- for(register int i=1;i<=n;++i)
- if(fabs(lx[x]+ly[i]-dis[x][i])<1e-9&&!t[i])
- {
- t[i]=1;
- if(!link[i]||dfs(link[i]))
- {
- link[i]=x;
- return true;
- }
- }
- return false;
- }
- inline void update()
- {
- double a=23333333;
- for(register int i=1;i<=n;++i)
- if(s[i])
- for(register int j=1;j<=n;++j)
- if(!t[j])
- a=Min(a,lx[i]+ly[j]-dis[i][j]);
- for(register int i=1;i<=n;++i)
- {
- if(s[i])
- lx[i]-=a;
- if(t[i])
- ly[i]+=a;
- }
- }
- inline void KM()
- {
- for(register int i=1;i<=n;++i)
- {
- link[i]=lx[i]=ly[i]=0;
- for(register int j=1;j<=n;++j)
- lx[i]=Max(lx[i],dis[i][j]);
- }
- for(register int i=1;i<=n;++i)
- while(19260817)
- {
- for(register int j=1;j<=n;++j)
- s[j]=t[j]=0;
- if(dfs(i))
- break;
- else
- update();
- }
- }
- inline double getdis(register int x,register int y)
- {
- return sqrt(pow(X1[x]-X2[y],2)+pow(Y1[x]-Y2[y],2));
- }
- int main()
- {
- while(scanf("%d",&n)!=EOF)
- {
- for(register int i=1;i<=n;++i)
- scanf("%lf %lf",&X1[i],&Y1[i]);
- for(register int i=1;i<=n;++i)
- scanf("%lf %lf",&X2[i],&Y2[i]);
- for(register int i=1;i<=n;++i)
- for(register int j=1;j<=n;++j)
- dis[j][i]=-getdis(i,j);
- KM();
- for(register int i=1;i<=n;++i)
- write(link[i]),puts("");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2876872.html