前言
显然,这是一道分数规划问题
传送门 :
思路
分数规划,无非就是列出表达式,化简表达式,二分出答案这几个步骤
但是对于建边我们需要考虑优化,如果用全部单词建边的话显然 1 e 5 ∗ 1 e 5 1e5*1e5 1e5∗1e5失智。
题中有提到只考虑头尾两个那么我们就可以使用头尾两个建边即可
最后再 c h e c k check check的时候加一个边界判断即可
CODE
struct node
{
int to,val;
};
vector<node> g[N];
char ch[1010];
double dist[N];
bool st[N];
int cnt[N];
queue<int> 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 < 676;++i){
q.push(i);
st[i] = true;
}
dist[1] = 0;
int count = 0;
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(auto x :g[t]){
int j = x.to;
int w = x.val;
if(dist[j] < dist[t] + w - mid * 1){
dist[j] = dist[t] + w - mid * 1;
cnt[j] = cnt[t] + 1;
if(++count > 10000) return true;
if(cnt[j] >= N) return true;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
void solve()
{
while(cin>>n,n)
{
for(int i=1;i<=N;i++)
g[i].clear();
for(int i = 0 ;i<n;i++)
{
cin>>ch;
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<<"No solution"<<endl;
}
else
{
double l = 0 ,r=1000;
while(r - l>=eps)
{
double mid = (l+r)/2;
if(check(mid)) l = mid;
else r=mid;
}
printf("%.2lf\n",r);
//cout<<r<<endl;
}
}
}