这道题的意思是给你一个图， 有点权和边权， 你的任务是求一个圈， 使得这个圈的点权和比边权和最大，我们依然可以使用01规划的知识， 将一条边的权值变为ai-mid*bi, 看看这个图里面有没有正环， 有的话说明还存在更优的解， 这里的正环问题可以将边权值取反变成负环问题， 代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const double eps = 1e-4; const int maxn = 1000 + 10; const int inf = 0x3fffffff; int n, m; double vw[maxn]; struct edge{ int v; double ew; }; vector<edge> G[maxn]; bool inque[maxn]; //是否在队列中 double dis[maxn]; //最短路长度 int cnt[maxn]; //入队次数 bool spfa(double mid) { for(int i=1; i<=n; i++) { inque[i] = false; dis[i] = (double)inf; cnt[i] = 0; } queue<int> que; que.push(1); inque[1]=true; dis[1]=0; while(!que.empty()) { int u = que.front(); que.pop(); inque[u]=false; for(int i=0; i<G[u].size(); i++) { int v=G[u][i].v, tpw=G[u][i].ew; double w = tpw*mid-vw[u]; if(dis[v]>dis[u]+w) { dis[v] = dis[u]+w; if(!inque[v]) { que.push(v); cnt[v]++; if(cnt[v]>n) return true; //存在负圈 } } } } return false; //不存在 } int main() { scanf("%d%d", &n, &m); double high = 0; for(int i=1; i<=n; i++) scanf("%lf", &vw[i]), high+=vw[i]; for(int i=0; i<m; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); G[u].push_back((edge){v, (double)c}); } double l=0, r=high+5; while(r-l >= eps) { double mid = (l+r)/2.0; bool tp = spfa(mid); //printf("l=%.3f, r=%.3f, mid=%.3f, tp=%d ", l, r, mid, tp); if(tp) l=mid; else r=mid; } printf("%.2f ", l); return 0; }