P4951 24pts求助
查看原帖
P4951 24pts求助
1145044
ichenyubo楼主2024/12/6 17:24
#include<bits/stdc++.h>
using namespace std;
int n,m,F,f[405],sumt,sumc;
bool conb[405];
int conc;
struct Edge{
	int u,v,cost,time;
	double w;
	void read() {
		cin>>u>>v>>cost>>time;
		w=1.000*cost/time;
	}
}e[10005];
int find(int x) {
	return f[x]=(f[x]==x)?x:find(f[x]);
}
bool cmp(Edge a,Edge b) {
	if(a.cost!=b.cost) return a.cost>b.cost;
	return a.time<b.time;
}
int main() {
	cin>>n>>m>>F;
	for(int i=1;i<=m;i++) {
		e[i].read();
	}
	for(int i=1;i<=n;i++) {
		f[i]=i;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++) {
		int fu=find(e[i].u),fv=find(e[i].v);
		if(fu!=fv) {
			sumt+=e[i].time,sumc+=e[i].cost;
			f[fu]=fv;
			if(!conb[e[i].u]){
				conb[e[i].u]=true;
				conc++;
			}
			if(!conb[e[i].v]){
				conb[e[i].v]=true;
				conc++;
			}
			if(conc==n) {
				printf("%.4lf",min(F*1.00,(1.00*(abs(F-sumc)))/(1.00*sumt)));
//				cout<<sumc<<" "<<sumt<<" "<<F-sumc; 
			}
		}
	}
	return 0;
}
2024/12/6 17:24
加载中...