「UVA1411」Ants-巨人与鬼
//题没输出玩，再来一张
翻译成中文就是：
思路（考虑到这道题比较难，就上个思路吧）
分治代码：
下面展示一些 内联代码片。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=505;
#define inf 999999999
int n,ax[maxn],ay[maxn],bx[maxn],by[maxn];
int S,T,h[maxn*2],edgenum=1,maxflow;
int flow[maxn*2],vis[maxn*2],pre[maxn*2],last[maxn*2];
double dis[maxn*2];
queue<int>q;
struct node
{int end,nxt,v;double s;
}e[200005];
void add(int a,int b,int v,double s)
{e[++edgenum].end=b;e[edgenum].v=v;e[edgenum].s=s;e[edgenum].nxt=h[a];h[a]=edgenum;
}
double askdis(int i,int j)
{double x=abs(ax[i]-bx[j]),y=abs(ay[i]-by[j]);return sqrt(x*x+y*y);
}
bool spfa()
{for(int i=S;i<=T;i++) {dis[i]=inf;}memset(vis,0,sizeof(vis));q.push(S);dis[S]=0;vis[S]=1;flow[S]=inf;pre[T]=-1;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=h[u];i;i=e[i].nxt){int v=e[i].end;if(e[i].v&&dis[v]>dis[u]+e[i].s){dis[v]=dis[u]+e[i].s;pre[v]=u;last[v]=i;flow[v]=min(flow[u],e[i].v);if(!vis[v]) {vis[v]=1;q.push(v);}}}}return pre[T]!=-1;
}int main()
{scanf("%d",&n);S=0;T=2*n+1;for(int i=1;i<=n;i++) scanf("%d%d",&ax[i],&ay[i]);for(int i=1;i<=n;i++) scanf("%d%d",&bx[i],&by[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){double clil=askdis(i,j);add(i,j+n,1,clil);add(j+n,i,0,-clil);}for(int i=1;i<=n;i++) add(S,i,1,0),add(i,S,0,0);for(int i=1;i<=n;i++) add(i+n,T,1,0),add(T,i+n,0,0);while(spfa()){int u=T;maxflow+=flow[T];while(u!=S){int i=last[u];e[last[u]].v-=flow[T];e[last[u]^1].v+=flow[T];u=pre[u];}}for(int i=1;i<=n;i++)for(int j=h[i];j;j=e[j].nxt){int v=e[j].end;if(!e[j].v){printf("%d\n",v-n);break;}}return 0;
}