万网站,天眼查询个人信息,表白网页生成软件下载,企业做网站的申请报告PS:此题数组名皆引用#xff1a;戳我 题目大意#xff1a;有n个点m条有向边的图#xff0c;边上有花费#xff0c;点上有收益#xff0c;点可以多次经过#xff0c;但是收益不叠加#xff0c;边也可以多次经过#xff0c;但是费用叠加。求一个环使得收益和/花费和最大戳我 题目大意有n个点m条有向边的图边上有花费点上有收益点可以多次经过但是收益不叠加边也可以多次经过但是费用叠加。求一个环使得收益和/花费和最大输出这个比值。 显然这就是经典的分数规划题啊就是最优比率环那么就二分答案将所有边uv的边权改为【v的点权-uv原边权*mid】因为d[i]a[i]-L*b[i]然后判一下是否有正环有的话就说明有更优的答案F(L)sigma(a[i]*x[i])-L*sigma(b[i]*x[i])0即sigma(a[i]*x[i])/sigma(b[i]*x[i])L缩小范围继续二分。判正环有够别扭的那就全部改成相反数然后判负环吧233333 代码如下 #includeiostream
#includecstring
#includecstdlib
#includecstdio
#includequeue
using namespace std;
struct zs{int too,pre;double dis;}e[10001];
struct poi{int pos;double dis;};
priority_queuepoiq;
bool operator (poi a,poi b){return a.dis-b.dis1e-3;}
int n,m,x,y,now,tot,num[1001],last[1001];
bool v[1001];
double l,r,mid,dis[1001],fun[1001];
bool spfa(int x)
{for(int i1;in;i)dis[i]23333333;v[x]true;q.push((poi){1,0});dis[1]0;while(!q.empty()){int i,too;for(ilast[nowq.top().pos],tooe[i].too,q.pop();i;ie[i].pre,tooe[i].too){double diste[i].dis*mid-fun[too];if(dis[too]-dis[now]-dist1e-3){dis[too]dis[now]dist;if(!v[too])v[too]1,q.push((poi){too,e[i].dis}),num[too];if(num[too]233)return 1;}}v[now]0;}return 0;
}
int main()
{scanf(%d %d,n,m);for(int i1;in;i)scanf(%lf,fun[i]);for(int i1;im;i){scanf(%d %d %lf,x,y,e[tot].dis);e[tot].tooy;e[tot].prelast[x];last[x]tot;}l0;r10000;while(r-l1e-3){memset(v,0,sizeof(v));memset(num,0,sizeof(num));mid(lr)/2;if(spfa(1))lmid;else rmid;}printf(%.2lf,l);
} View Code 转载于:https://www.cnblogs.com/Sakits/p/5469300.html
