poj 3565 Ants KM

题意：

给n只蚂蚁和n课苹果树的坐标，要让每只蚂蚁去一棵苹果树，路线不能重复，求一种可行方案。

分析：

当某种匹配可行时蚂蚁所走的距离和是最小的，可以直接用KM算法求二分图最小权值匹配。还有一种做法是先假定一种匹配，如果其中有交叉就进行调整。

代码：

//poj 3565
//sep9
#include 
  
   
#include 
   
     using namespace std; const int maxN=128; const double INF=999999999.0; double w[maxN][maxN],lx[maxN],ly[maxN],slack[maxN]; int linky[maxN]; int visx[maxN],visy[maxN]; int nx,ny; double antX[maxN],antY[maxN],appleX[maxN],appleY[maxN]; int ans[maxN]; bool find(int x) { visx[x]=true; for(int y=0;y
    
     t) slack[y]=t; } return false; } int KM() { int i,j; memset(linky,-1,sizeof(linky)); for(i=0;i
     
      lx[i]) lx[i]=w[i][j]; for(int x=0;x