C++14(g++5.4) 解法, 执行用时: 397ms, 内存消耗: 11564K, 提交时间: 2020-01-01 17:36:50

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 26*26;



typedef pair<int, int> pii;
vector<pii> G[MAXN];
int getId(string s) {
  return (s[0]-'a') * 26 + s[1]-'a'; 
}
double dis[MAXN];
bool inq[MAXN];

bool dfs(int s, double limit) {
  inq[s] = true;
  for (auto it: G[s]) {
    int t = it.first;
    double w = it.second - limit;
    if (dis[t] >= dis[s] + w) continue;
    if (inq[t]) return true;
    dis[t] = dis[s] + w;
    if (dfs(t, limit)) return true;
  }
  inq[s] = false;
  return false;
}

bool spfa(int s, double limit) {
  memset(inq, 0, sizeof(inq));
  memset(dis, 0, sizeof(dis));
  return dfs(s, limit);
}


bool isValid(double limit) {
  for (int i = 0; i < 26*26; i++) if (spfa(i, limit)) return true;
  return false;
}

int main()
{
  ios_base::sync_with_stdio(false);
  int n;
  while (cin >> n && n) {
    for (int i = 0; i < MAXN; i++) G[i].clear();
    vector<string> words(n);
    for (auto &w: words) cin >> w;
    map<string, vector<int>> pre;
    for (int i = 0; i < n; i++) if (words[i].size() >= 2) pre[words[i].substr(0, 2)].push_back(i);
    for (int s = 0; s < n; s++) {
      if (words[s].size() < 2) continue;
      string c2 = words[s].substr(words[s].size() - 2);
      for (auto t: pre[c2]) G[getId(words[s])].push_back({getId(words[t]), words[s].size()});
    }
    double lo = 0, hi = 1024;
    while (hi - lo >= 1e-4) {
      double mid = (lo + hi) / 2;
      if (isValid(mid)) lo = mid;
      else hi = mid;
    }
    if (lo == 0) cout << "No solution" << endl;
    else cout << fixed << setprecision(2) << lo << endl;
  }
}

C++(clang++ 11.0.1) 解法, 执行用时: 240ms, 内存消耗: 624K, 提交时间: 2023-07-18 16:51:20

#include<bits/stdc++.h>

using namespace std;

map<string,int> tbl;
int n=26*26,m;
int h[700];
int to[100010];
int nt[100010];
int w[100010];
int idx;

void add(int x,int y,int z){
	to[idx]=y;
	nt[idx]=h[x];
	w[idx]=z;
	h[x]=idx;
	idx++;
}

bool v[700];
double d[700];

bool spfa(int u,double mid){
	v[u]=true;
	for(int i=h[u];i!=-1;i=nt[i]){
		int j=to[i];
		double z=w[i]-mid*1;
		if(d[j]<d[u]+z){
			d[j]=d[u]+z;
			if(v[j]||spfa(j,mid)) return true;
		}
	}
	v[u]=false;
	return false;
}

bool check(double mid){
	memset(v,0,sizeof(v));
	memset(d,0,sizeof(d));
	for(int i=1;i<=n;i++){
		if(spfa(i,mid)) return true;
	}
	return false;
}

void init(){
	idx=0;
	memset(h,-1,sizeof(h));
}

int main(){
	for(int i=0;i<26;i++){
		for(int j=0;j<26;j++){
			string tmp;
			tmp+=char(i+'a');
			tmp+=char(j+'a');
			tbl[tmp]=i*26+j+1;
		}
	}
	while(true){
		init();
		cin>>m;
		if(m==0) break;
		while(m--){
			string s;
			cin>>s;
			if(s.size()<2) continue;
			int x=tbl[s.substr(0,2)];
			int y=tbl[s.substr(s.size()-2)];
			add(x,y,s.size());
		}
		double l=0,r=1000,mid;
		while(r-l>=1e-6){
			mid=(l+r)/2;
			if(check(mid)) l=mid;
			else r=mid;
		}
		if(fabs(r)<=1e-6){
			puts("No solution");
		}
		else printf("%.2lf\n",r);
	}
	
	return 0;
}