网站开发与设计多少钱一个网站,简单ppt模板下载免费完整版,淘宝网页设计培训班,网站建设的语言与工具题意#xff1a;
L个点#xff0c;P边的点边带权的有向图#xff0c;求一个环点权和与边权和比值的最大值。
题解#xff1a;
01分数规划判负环 详细看这里
还是套用01分数规划模型#xff0c;点权为value[i],边权为cost[u],一个环为C#xff0c;问题要求最大化
最…题意
L个点P边的点边带权的有向图求一个环点权和与边权和比值的最大值。
题解
01分数规划判负环 详细看这里
还是套用01分数规划模型点权为value[i],边权为cost[u],一个环为C问题要求最大化
最小化就是符号倒过来 和之前一样处理设当前答案为r设边权为dis[i] r * ∑cost[i] - ∑value[i] 如果r r *,则说明至少存在一个环d[i] 0,也就是存在负权回环边权值并不是提前算好而是在更新路径的时候从哪个点访问到这个边的就将这条边设为相应点权与边权的对应值 如果r r * ,则不存在负环 判负环一半用spfa方法一个点不能入队n次否则有负环一条最短路径长度不能到n否则有负环。貌似后者更快
代码
#includealgorithm
#includeiostream
#includecstring
#includecstdio
#includecmath
using namespace std;
#define N 1005
#define E 5005const double eps1e-6;
int n,m,x,y;
int tot,point[N],nxt[E],v[E];double c[E];
double val[N],e[E],ans;
double dis[N];
int cnt[N];bool vis[N];
int q[N];void add(int x,int y)
{tot; nxt[tot]point[x]; point[x]tot; v[tot]y;
}
bool spfa()
{memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));;memset(cnt,0,sizeof(cnt));int head0,tail0;for (int i1;in;i){vis[i]1;cnt[i];q[(tail)%n]i;}while (head!tail){int nowq[(head)%n];vis[now]0;for (int ipoint[now];i;inxt[i])if (dis[v[i]]dis[now]c[i]){dis[v[i]]dis[now]c[i];if (!vis[v[i]]){vis[v[i]]1;cnt[v[i]];if (cnt[v[i]]n) return true;q[(tail)%n]v[i];}}}return false;
}
bool check(double L)
{for (int i1;itot;i)c[i]val[v[i]]-L*e[i];return spfa();
}
double find()
{double l0.0,r1e4,mid,ans0.0;while (r-leps){mid(lr)/2.0;if (check(mid)) anslmid;else rmid;}return ans;
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i) scanf(%lf,val[i]);for (int i1;im;i){scanf(%d%d%lf,x,y,e[i]);add(x,y);}ansfind();printf(%.2lf\n,ans);
}
