题目链接:Click here~~
题意:
给出一个有向图,找一条环,使得环上的 点权之和/边权之和 最大。
解题思路:
此题仍是 01分数规划 的应用,和 最优比例生成树 也比较像。
令 L = ∑a[i]*x[i] / ∑b[i]*x[i](x[i] = {0,1} 表示是否选取 i 这条边,a[i] 表示 i 这条边始点或末点的点权,b[i] 表示 i 这条边的边权,路径必须是回路)。
转成另外一个问题,我们令 Z = ∑( a[i] - L * b[i] ) * x[i] 最大。即令 Z' = ∑( L * b[i] - a[i] ) * x[i] 最小。
如果对于某个 L ,Z' 的最小值小于0,说明 L 小于 Lmax。而判断 Z' 的最小值是否小于0等价于判断图中是否有负环。如此,问题解决了。
Ps. Z => Z‘ 以及之后的分析很关键,要仔细思考。
#include <queue> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1e3 + 5; template<int N,int M> struct Graph { int top; struct Vertex{ int head; }V[N]; struct Edge{ int v,next; double w; }E[M]; void init(){ memset(V,-1,sizeof(V)); top = 0; } void add_edge(int u,int v,double w){ E[top].v = v; E[top].w = w; E[top].next = V[u].head; V[u].head = top++; } }; Graph<1003,5003> g,gg; int wp[N]; void build(int n,double L) { gg.init(); for(int u=1;u<=n;u++) { for(int i=g.V[u].head;~i;i=g.E[i].next) { int v = g.E[i].v; double w = g.E[i].w; gg.add_edge(u,v,L*w-wp[v]); } } } int inqCnt[N]; double d[N]; bool inq[N]; bool spfa(int s,int n) { memset(inqCnt,0,sizeof(inqCnt)); memset(inq,false,sizeof(inq)); memset(d,127,sizeof(d)); queue<int> Q; Q.push(s); inq[s] = true; inqCnt[s] = 1; d[s] = 0; while(!Q.empty()) { int u = Q.front(); for(int i=gg.V[u].head;~i;i=gg.E[i].next) { int v = gg.E[i].v; double w = gg.E[i].w; if(d[u] + w < d[v]) { d[v] = d[u] + w; if(!inq[v]) { Q.push(v); inq[v] = true; if(++inqCnt[v] >= n) return false; } } } Q.pop(); inq[u] = false; } return true; } const double eps = 1e-4; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { g.init(); for(int i=1;i<=n;i++) scanf("%d",&wp[i]); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g.add_edge(u,v,w); } double l = 0 , r = 1000; while(r-l > eps) { double mid = (l+r) / 2; build(n,mid); if(spfa(1,n)) r = mid; else l = mid; } printf("%.2f\n",r); } return 0; }