luoguP2526_[SHOI2001]小狗散步_二分图匹配
题意：
Grant喜欢带着他的小狗Pandog散步。Grant以一定的速度沿着固定路线走，该路线可能自交。Pandog喜欢游览沿途的景点，不过会在给定的N个点和主人相遇。小狗和主人同时从(X1，Y1)点出发，并同时在(Xn，Yn)点汇合。小狗的速度最快是Grant的两倍。当主人从一个点以直线走向另一个点时，Pandog跑向一个它感兴趣的景点。Pandog每次与主人相遇之前最多只去一个景点。
分析：
我们可以把人每次走的一条路径当作点，显然狗只能从出发点走到符合条件的部分点，把这两个点连边，表示狗要么跟人走，要么选择一条能走的路走。
求二分图最大匹配即可
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
#define N 600
#define du double
#define S (n+m+1)
#define T (n+m+2)
#define inf 100000000
int head[N],to[N*N<<1],nxt[N*N<<1],flow[N*N<<1],cnt=1,n,m,dep[N];
inline void add(int u,int v,int f){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;flow[cnt]=f;
to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;flow[cnt]=0;
}
struct P{
int x,y;
}a[N],b[N];
du dis(P u,P v){
return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));
}
bool bfs(){
queue <int> q;
q.push(S);memset(dep,0,sizeof(dep));
dep[S]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i]){
if(!dep[to[i]]&&flow[i]){
dep[to[i]]=dep[x]+1;
if(to[i]==T)return 1;
q.push(to[i]);
}
}
}
return 0;
}
int dfs(int x,int mf){
if(x==T)return mf;
int nf=0;
for(int i=head[x];i;i=nxt[i]){
if(dep[to[i]]==dep[x]+1&&flow[i]){
int tmp=dfs(to[i],min(flow[i],mf-nf));
nf+=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
if(nf==mf)break;
}
}
dep[x]=0;return nf;
}
void dinic(){
int ans=0,f;
while(bfs())while(f=dfs(S,inf))ans+=f;
printf("%d\n",ans+n);
for(int i=1;i<n;i++){
printf("%d %d ",a[i].x,a[i].y);
for(int j=head[i];j;j=nxt[j]){
if(to[j]!=S&&flow[j]==0){
printf("%d %d ",b[to[j]-n+1].x,b[to[j]-n+1].y);
}
}
}
printf("%d %d",a[n].x,a[n].y);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
if(i^n)add(S,i,1);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&b[i].x,&b[i].y);
add(i+n-1,T,1);
}
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
if(dis(a[i],a[i+1])>=(dis(a[i],b[j])+dis(a[i+1],b[j]))/2){
add(i,j+n-1,1);
}
}
}
dinic();
}