想问下不能用最小生成树kru的方法么?只有60分!!
查看原帖
想问下不能用最小生成树kru的方法么?只有60分!!
458522
wjslaity楼主2021/7/15 20:13
#include<bits/stdc++.h>//kru
using namespace std;
typedef long long ll;
struct node{
	ll u,v,c,t,e;
}cnt[1005];
ll n,m,f;
double res1=0,res2=0;
ll pre[405];
void init(){
	for(int i=1;i<=n;i++) pre[i]=i;
}
int Find(int x){
	int r=x;
	while(r!=pre[r]){
		r=pre[r];
	}
	int i=x,j;
	while(i!=pre[r]){
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;
}

bool cmp(node a,node b){
	return a.e<b.e;
}

int main(){
	cin >> n >> m >> f;
	init();
	for(int i=1;i<=m;i++){
		cin >> cnt[i].u >> cnt[i].v >> cnt[i].c >> cnt[i].t;
		cnt[i].e=cnt[i].c*cnt[i].t;
	}
	
	sort(cnt+1,cnt+m+1,cmp);
	
	for(int i=1;i<=m;i++){
		node a=cnt[i];
		int fx=Find(a.u),fy=Find(a.v);
		if(fx!=fy){
			pre[fx]=fy;
			res1+=a.c;
			res2+=a.t;
		}
	}
	double res;
	if(res1>=f) res=0;
	else {
		res=(f-res1)*1.0/res2;
	}
	printf("%.4lf\n",res);
	return 0;
} 
2021/7/15 20:13
加载中...