[Acwing]1165. 单词环 spfa判断负环+分数规划

前言

显然,这是一道分数规划问题 传送门 :

思路

分数规划,无非就是列出表达式,化简表达式,二分出答案这几个步骤

但是对于建边我们需要考虑优化,如果用全部单词建边的话显然 1 e 5 ∗ 1 e 5 1e5*1e5 1e5∗1e5失智。

题中有提到只考虑头尾两个那么我们就可以使用头尾两个建边即可

最后再 c h e c k check check的时候加一个边界判断即可

CODE

struct node
{
	int to,val;
};
vector g[N];
char ch[1010];
double dist[N];
bool st[N];
int cnt[N];
queue q;

void cal()
{

}

bool check(double mid){
    memset(st,0,sizeof st);
    memset(dist,0,sizeof dist); //求最长路
    memset(cnt,0,sizeof cnt);

    for(int i = 0;i = N) return true;

                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

void solve()
{
    while(cin>>n,n)
	{
		for(int i=1;ich;
			int len = strlen(ch);

			if(len>=2 )
			{
				int a = (ch[0] - 'a') * 26 + (ch[1] - 'a');
                int b = (ch[len - 2] - 'a') * 26 + (ch[len - 1] - 'a');
        		g[a].pb({b,len});
			}
		}

		if(!check(0))
		{
			cout