luoguP2526_[SHOI2001]小狗散步_二分图匹配

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();
}
上一篇:对jquery操作复选框


下一篇:回顾Ado.Net