本文主要是介绍POJ 3621 最优比率生成环 01分数规划问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意就是找到一个环使得顶点权值之和与边权之和的比率最大
首先,需要注意的是题目要求可以从任意一点开始,网上很多解题报告默认的从1点开始,虽然过了此题,但是显然是不太对的
由于题目是求的max,那么在边权变形后,用 SPFA求最长路,看是否出现正环, 然后根据这个进行二分查找。
如果不懂图是怎么构建的,可以看一下01规划具体是怎么做的。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define MAXN 1005
#define MAXM 50005
#define INF 1000000000
#define eps 1e-6
using namespace std;
struct node
{int v, next;double w;
}edge[MAXM];
int head[MAXN], e, vis[MAXN], q[50 * MAXM], c[MAXN];
int n, m;
double d[MAXN], val[MAXN];
void insert(int x, int y, double w)
{edge[e].v = y;edge[e].w = w;edge[e].next = head[x];head[x] = e++;
}
bool spfa(double mid)
{int h = 0, t = 0;for(int i = 1; i <= n; i++){vis
这篇关于POJ 3621 最优比率生成环 01分数规划问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!