这份代码的建图方式可以通过本题，但若采用注释中的建图方式就会 TLE。生成了几组数据后发现是 spfa 之后的增广路成环了，导致 EK 的时候死循环（奇怪的是明明有环 spfa 却没死）。

两种建图方式我认为没有本质区别，只是把图倒过来而已。求问造成这种现象的原因。

#include<bits/stdc++.h>
using namespace std;
const double INF=1e6,eps=1e-8;
const int P=100010,E=1000010;
int S,T,head[P],ver[E],ne[E],edge[E],idx=2;double cost[E];
void add(int x,int y,int z,double c){
	ver[idx]=y,edge[idx]=z,cost[idx]=c,ne[idx]=head[x],head[x]=idx++;
	ver[idx]=x,edge[idx]=0,cost[idx]=-c,ne[idx]=head[y],head[y]=idx++;
}
queue<int>q;
bool vis[P];
int now[P],pre[P],fl[P];double dis[P];
bool spfa(){
	for(int i=1;i<=T;i++)dis[i]=INF;
	memcpy(now,head,sizeof now);
	q.push(S);dis[S]=0,pre[S]=0;
	while(q.size()){
		int x=q.front();q.pop();
//		cerr<<"VIS"<<x<<'\n';
		vis[x]=0;
		for(int i=head[x];i;i=ne[i])
			if(edge[i]&&dis[x]+cost[i]<dis[ver[i]]){
				dis[ver[i]]=dis[x]+cost[i];
				fl[ver[i]]=min(fl[x],edge[i]);
				pre[ver[i]]=i;
				if(!vis[ver[i]])vis[ver[i]]=1,q.push(ver[i]);
			}
	}
	return dis[T]!=INF;
}
double res;
int EK(){
	fl[S]=0x3f3f3f3f;
	if(!spfa())return false;
	int x=T,flow=fl[T];
	while(x!=S){
		res+=flow*cost[pre[x]];
		edge[pre[x]]-=flow,edge[pre[x]^1]+=flow;
		x=ver[pre[x]^1];
//		cerr<<x<<'\n';
	}
	return flow;
}
int n;
struct Point{
	int x,y;
}p[410];
double Dis(Point&a,Point&b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
	S=3*n+1,T=S+1;
	for(int i=1;i<=n;i++){
//		add(S,i,1,0);		
//		for(int j=1;j<=n;j++)
//			if(p[j].y>p[i].y){
//				add(i,j+n,1,Dis(p[i],p[j]));
//			}
//		add(i+n,T,2,0);
		add(S,i,2,0);
		for(int j=1;j<=n;j++)
			if(p[j].y<p[i].y){
				add(i,j+n,1,Dis(p[i],p[j]));
			}
		add(i+n,T,1,0);
	}
	int tmp,flow=0;
	while((tmp=EK()))flow+=tmp;
	if(flow!=n-1)cout<<"-1\n";
	else cout<<fixed<<setprecision(15)<<res;
}

附一个数据生成器：

#include<bits/stdc++.h>
using namespace std;
mt19937 rd(chrono::high_resolution_clock().now().time_since_epoch().count());
int random(int x){
	return rd()%x;
}
int main(){
	freopen("data.in","w",stdout);
	int n=400;
	cout<<n<<'\n';
	for(int i=1;i<=n;i++){
		cout<<random(2001)-1000<<' '<<random(2001)-1000<<'\n';
	}
}