【LA4043 训练指南】蚂蚁 【二分图最佳完美匹配，费用流】

题意

给出n个白点和n个黑点的坐标，要求用n条不相交的线段把他们连接起来，其中每条线段恰好连接一个白点和一个黑点，每个点恰好连接一条线段。

分析

结点分黑白，很容易想到二分图。其中每个白点对应一个X结点，每个黑点对应一个Y点，每个黑点和每个白点相连，权值等于二者的欧几里得距离，建模之后，最佳完美匹配就是问题的解。

为什么用费用流而不用KM呢，因为我不会···

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <vector>

 #include <queue>

 #include <cmath>

 using namespace std;

 const int maxN=;

 const int maxm=+;

 const int INF=;

 int n;

 int ax[maxN],bx[maxN],ay[maxN],by[maxN];

 struct MCMF{

     int head[maxN],to[maxm],Next[maxm],from[maxm],flow[maxm],cap[maxm];

     double cost[maxm];

     int n,m,s,t,sz;

     int inq[maxN];

     double d[maxN];

     int p[maxN];

     int a[maxN];

     void init(int n){

         this->n=n;

         sz=-;

         memset(head,-,sizeof(head));

     }

     void AddEdge(int a,int b,int ca,double co){

         ++sz;

         to[sz]=b,from[sz]=a,Next[sz]=head[a],head[a]=sz;

         flow[sz]=,cap[sz]=ca,cost[sz]=co;

         ++sz;

         to[sz]=a,from[sz]=b,Next[sz]=head[b],head[b]=sz;

         flow[sz]=ca,cap[sz]=ca,cost[sz]=-co;

     }

     bool BellmanFord(int s,int t,int &Flow,double &Cost){

         for(int i=;i<=n;i++)d[i]=INF;

         memset(inq,,sizeof(inq));

         d[s]=;inq[s]=;p[s]=-;a[s]=INF;

         queue<int>Q;

         Q.push(s);

         while(!Q.empty()){

             int u=Q.front();Q.pop();

             inq[u]=;

             for(int i=head[u];i!=-;i=Next[i]){

                 int v=to[i];

                 if(cap[i]>flow[i]&&d[v]>d[u]+cost[i]){

                     d[v]=d[u]+cost[i];

                     p[v]=i;

                     a[v]=min(a[u],cap[i]-flow[i]);

                     if(!inq[v]){

                         Q.push(v);

                         inq[v]=;

                     }

                 }

             }

         }

         if(d[t]==INF)return false;

         Flow+=a[t];

         Cost+=d[t]*(double)a[t];

         int u=t;

         while(u!=s){

             flow[p[u]]+=a[t];

             flow[p[u]^]-=a[t];

             u=from[p[u]];

         }

         return true;

     }

     double Mincost(int s,int t){

         int Flow=;

         double Cost=;

         while(BellmanFord(s,t,Flow,Cost));

         return Cost;

     }

 }mcmf;

 double dist(int X,int Y){

     return sqrt((double)(ax[X]-bx[Y])*(ax[X]-bx[Y])+(double)(ay[X]-by[Y])*(ay[X]-by[Y]));

 }

 int main(){

     while(scanf("%d",&n)!=EOF){

         for(int i=;i<=n;i++)

             scanf("%d%d",&ax[i],&ay[i]);

         for(int i=;i<=n;i++)

             scanf("%d%d",&bx[i],&by[i]);

         mcmf.init(*n+);

         for(int i=;i<=n;i++)

             mcmf.AddEdge(,i,,);

         for(int i=;i<=n;i++)

             mcmf.AddEdge(i+n,*n+,,);

         for(int i=;i<=n;i++){

             for(int j=;j<=n;j++){

                 mcmf.AddEdge(i,j+n,,dist(i,j));

             }

         }

         mcmf.Mincost(,*n+);

         for(int i=;i<=n;i++){

             for(int j=mcmf.head[i];j!=-;j=mcmf.Next[j]){

                 if(j%)continue;

                 int v=mcmf.to[j];

                 if(mcmf.cap[j]==mcmf.flow[j]){

                     printf("%d\n",v-n);

                     break;

                 }

             }

         }

     }

     return ;

 }