MnZn01分数规划WA #10求助(有注释)
查看原帖
MnZn01分数规划WA #10求助(有注释)
510555
ImposterAnYu楼主2024/8/7 10:35
#include <bits/stdc++.h>
#define int1 int
#define N 100000
#define M 200000
#define exp 1e-8
using namespace std;
int1 n,m,i,f[N + 5];//点数、边数、i、父亲(并查集用) 
double l,r,mid,cost[M + 5],tim[M + 5];//二分左边界、右边界、中点;道路的花费和时间 
int1 bs;//边数 
struct Edge{
	int1 x,y,id;
	double w;
} e[M + 5];
bool cmp(Edge x,Edge y){//比较器 
	return x.w < y.w;
}
bool cmp2(Edge x,Edge y){//还原边的顺序 
	return x.id < y.id;
}
int1 read(){//快读 
	int1 x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)){
		if (ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while (isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void uprint(int1 x){//快写 
	if (x >= 10){
		uprint(x / 10);
	}
	putchar(x % 10 ^ 48);
	return ;
}
void print(int1 x){//快写 
	if (x < 0){
		putchar('-');
		x = -x;
	}
	uprint(x);
	return ;
}
void ps(int1 x){//快写 
	print(x);
	putchar(' ');
	return ;
}
void pe(int1 x){//快写 
	print(x);
	putchar('\n');
	return ;
}
void add_edge(int1 x,int1 y,double c,double t){
	cost[++bs] = c,tim[bs] = t;
	e[bs].x = x,e[bs].y = y,e[bs].id = bs;
	return ;
}
int1 find(int1 x){//找爸爸
	if(f[x] == x){
		return x;
	} 
	return f[x] = find(f[x]);
}
double kruskal(){//最小生成树(?) 
	sort(e + 1,e + bs + 1,cmp);//按边权排序 
	double s = 0;
	int1 i;
	for(i = 1; i <= n; i++){
		f[i] = i;//父亲初始化 
	}
	for(i = 1; i <= bs; i++){
		int1 fx = find(e[i].x),fy = find(e[i].y);
		if(fx == fy && e[i].w <= 0){//如果修这条边答案更优但在最小生成树里不修 
			s += e[i].w;//我照样要修 
		}
		if(fx != fy){//如果没联通 
			f[fy] = fx;//修 
			s += e[i].w;
		}
	}
	sort(e + 1,e + bs + 1,cmp2);//复原 
	return s;
}
bool check(double x){
//原理:sum(cost)/sum(time)<=x
//sum(cost)<=x*sum(time)
//sum(cost)-x*sum(time)<=0
//sum(cost-x*time)<=0
	for(int1 i = 1; i <= bs; i++){
		e[i].w = cost[i] - x * tim[i];//赋新边权 
	}
	double s = kruskal();
	return (s <= exp);//<=0即可 
}
int main(){
	n = read(),m = read();
	for(i = 1; i <= m; i++){
		int1 x = read() + 1,y = read() + 1;//把点从0~n-1变成1~n 
		double a = read() * 1.0,b = read() * 1.0;
		add_edge(x,y,a,b);//建边(?) 
	}
	l = 0.000001,r = 1000000;
	while(r - l > exp){
		mid = (l + r) / 2;
		if(check(mid)){//如果满足条件就改右边界(因为是求最小值) 
			r = mid;
		}else{
			l = mid;
		}
	}
	cout<< r << endl;
	return 0;
}

机房电脑上不去AT,看不到具体情况

2024/8/7 10:35
加载中...