长长的prim代码 WA #4求条
查看原帖
长长的prim代码 WA #4求条
752094
MornHus楼主2023/11/12 20:14
#include<bits/stdc++.h>
using namespace std;
#define maxn 2005
int n;
struct C{
	int x,y; 
}city[maxn]; 

struct L{
	int l,r;
}line[maxn];

int c[maxn];
int k[maxn];

long long dis[maxn];
bool vis[maxn];
typedef pair<long long ,pair<int,int> > pii;
priority_queue<pii,vector<pii>,greater<pii> >q;
int ans,tot;

inline long long getlen(int a,int b){
	return ((long long)(k[a]+k[b]))*((long long)(abs(city[a].x-city[b].x)+abs(city[a].y-city[b].y)));
}

int V,E;
int power_point[maxn];

void prim(){
	dis[0]=0;
	q.push(make_pair(0,make_pair(0,114514)));
	int now,d;
	while(!q.empty()&&tot!=n+1){
		int from=q.top().second.second;
		int now=q.top().second.first;
		int d=q.top().first;
		q.pop();
		if(vis[now])continue;
		vis[now]=1;
		if(now==0){
			tot++;
			ans+=d;
			for(int i=1;i<=n;i++){
				if(c[i]<dis[i]){
					dis[i]=c[i];
					q.push(make_pair(dis[i],make_pair(i,0)));	
				}
			}
		}else{
			tot++;
			ans+=d;
			for(int i=1;i<=n;i++){
				if(i==now)continue;
				int w=getlen(i,now);
				if(w<dis[i]){
					dis[i]=w;
					q.push(make_pair(dis[i],make_pair(i,now)));
				}
			}
		}
		if(from==114514)continue;
		if((now==0 || from==0)){
			power_point[++V]=max(now,from);
		}else{
			line[++E].l=min(now,from);
			line[E].r=max(now,from);
		}
		
	}
}
int main(){
    
	cin>>n;
    
	memset(dis,0x7f,sizeof(dis));
    for(int i=1;i<=n;i++)cin>>city[i].x>>city[i].y;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)cin>>k[i];
	
	prim();
	
	cout<<ans<<'\n';
	cout<<V<<'\n';
	for(int i=1;i<=V;i++){
		cout<<power_point[i]<<' ';
	}
	cout<<'\n'<<E<<'\n';
	for(int i=1;i<=E;i++){
		cout<<line[i].l<<' '<<line[i].r<<'\n';
	}
	return 0;
} 
/*

随时处理曼哈顿距离

考虑建虚边,连接到超级源点。边权为从c[i]

边数过多,考虑使用prim

prim复习完了,考虑一边 遍历 , 一边 建边 

要求输出
1. 最小生成树大小 ok 
2. 与超级原点连接点的点数 v(发电站个数)  考虑prim时统计 
3. 输出发电站 integers   考虑prim时记录 
4. 电缆个数 e(考虑树总边数减去发电站个数:n-v) 
5. 需建立的电缆  考虑prim时记录
 
*/
2023/11/12 20:14
加载中...