求调
查看原帖
求调
763878
Jerry_heng楼主2023/7/13 16:27
#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n,k,cnt,s,t,deep[20001],cur[20001],head[20001];
const int inf=1e8;
struct node{
	int to,nxt,w;
}edge[20001];
struct nodd{
	int x,y;
}a[20001],b[20001];
void add(int u,int v,int w){
	edge[cnt].to=v;
	edge[cnt].nxt=head[u];
	edge[cnt].w=w;
	head[u]=cnt++;
}
bool bfs(){
	memset(deep,0,sizeof deep);
	memcpy(cur,head,sizeof head);
	queue<int>q;
	q.push(s);
	deep[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(u==t)break;
		for(int i=head[u];~i;i=edge[i].nxt){
			int v=edge[i].to;
			if(deep[v]||edge[i].w==0)continue;
			deep[v]=deep[u]+1;
			q.push(v);
		}
	}
	return deep[t];
}
int dfs(int now,int f){
	if(t==now)return f;
	int flow=0;
	for(int i=cur[now];~i&&f;i=edge[i].nxt){
		int v=edge[i].to;
		cur[now]=i;
		if(deep[v]!=deep[now]+1||edge[i].w==0)continue;
		int c=dfs(v,min(f,edge[i].w));
		f-=c;flow+=c;
		edge[i].w-=c;edge[i^1].w+=c;
	}
	return flow;
}
int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	return ans;
}
double js(nodd p,nodd q){
	return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}
signed main(){
	cin>>n>>m;
	memset(head,-1,sizeof head);
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	for(int i=1;i<=m;i++)cin>>b[i].x>>b[i].y;
	s=0,t=n+m+1;
	for(int i=1;i<=n;i++)add(s,i,1),add(i,s,0);
	for(int i=1;i<=m;i++)add(i+n,t,1),add(t,i+n,0);
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			if(js(a[i],a[i+1])*2.0>=js(a[i],b[j])+js(a[i+1],b[j])){
				add(i,n+j,1);
				add(n+j,i,0);
			}
	cout<<dinic()+n<<endl;
	cout<<a[1].x<<" "<<a[1].y<<" ";
	for(int i=2;i<=n;i++){
		for(int j=head[i];~j;j=edge[j].nxt)
			if(edge[j].w==0&&edge[j].to!=s){
				cout<<b[edge[j].to-n].x<<" "<<b[edge[j].to-n].y<<" ";
				break;
			}
		cout<<a[i].x<<" "<<a[i].y<<" ";
	}
	return 0;
}
2023/7/13 16:27
加载中...