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;yt)
slack[y]=t;
}
return false;
}
int KM()
{
int i,j;
memset(linky,-1,sizeof(linky));
for(i=0;ilx[i])
lx[i]=w[i][j];
for(int x=0;x
