之前的题解是瞎扯,已于2020.1.9更新.
题意:求最大平均值环.

将边权取反之后求最小平均值环即可.求最小平均值环,01分数规划+判负环即可.

这题毒瘤,判负环要dfs-spfa,时间复杂度玄学.

/**********/省略快读
#define MAXN 300011
struct Edge
{
    ll v,nxt;
    double w;
}e[MAXN];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,double w)
{
    ++cnt;
    e[cnt].v=v,e[cnt].w=w;
    e[cnt].nxt=last[u],last[u]=cnt;
}

str a,cur,start;
std::map<str,ll>p;
ll value(char a)
{
    if(a=='S')return 1000;
    if(a=='G')return 500;
    if(a=='D')return 300;
    if(a=='T')return 200;
    return 150;
}

double dis[MAXN];
ll n=0;
bool vis[MAXN];
bool spfa(ll u,double k)
{
    vis[u]=1;
    for(ll i=last[u];i;i=e[i].nxt)
    {
        ll v=e[i].v;
        double w=u?e[i].w+k:0;
        if(dis[v]>dis[u]+w)
        {
            dis[v]=dis[u]+w;
            if(vis[v]||spfa(v,k))return 1;
        }
    }
    vis[u]=0;
    return 0;
}
bool negative_ring(double k)
{
    for(ll i=1;i<=n;++i)dis[i]=0x3f3f3f3f,vis[i]=0;
    for(ll i=1;i<=n;++i)
        if(spfa(i,k))return 1;
    return 0;
}
int main()
{
    std::ios::sync_with_stdio(0);
    ll m;
    std::cin>>m;
    for(ll i=1;i<=m;++i)
    {
        std::cin>>a;
        cur="";
        bool flag=0;
        ll sum=0;
        for(str::iterator it=a.begin();it!=a.end();++it)
            if((*it)=='-')
            {
                if(!flag)
                {
                    flag=1;
                    start=cur;
                }
                sum+=value(cur[0]);
                cur="";
            }
            else cur+=*it;
        sum+=value(cur[0]);
        if(!p.count(start))p[start]=++n;
        if(!p.count(cur))p[cur]=++n;
        adde(p[start],p[cur],-sum);
    }
    if(!negative_ring(0))puts("-1");
    else
    {
        double l=0,r=100000,mid;
        while(r-l>0.2)
        {
            mid=(l+r)/2.0;
            if(negative_ring(mid))l=mid;
            else r=mid;
        }
        printf("%.0lf",l);
    }
    return 0;
}