主要算法
最短路径快速算法SPFA
强连通图StronglyConnectedGraph
P1：虫洞Wormholes
题目描述
题目描述
John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John 的每个农场有 M 条小路（无向边）连接着 N（从 1 到 N 标号）块地，并有 W 个虫洞。
现在 John 想借助这些虫洞来回到过去（在出发时刻之前回到出发点），请你告诉他能办到吗。 John 将向你提供 F 个农场的地图。没有小路会耗费你超过 104秒的时间，当然也没有虫洞回帮你回到超过 10^4 秒以前。
输入
第一行，三个整数 N,M,W；
接下来 M 行，每行三个数 S,E,T，表示在标号为 S 的地与标号为 E 的地中间有一条用时 T 秒的小路；
接下来 W 行，每行三个数 S,E,T，表示在标号为 S 的地与标号为 E 的地中间有一条可以使 John 到达 T 秒前的虫洞。
输出
输出共 F 行，如果 John 能在第 i 个农场实现他的目标，就在第 i 行输出 YES，否则输出 NO。
样例输入1
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3样例输入2
3 2 1
1 2 3
2 3 4
3 1 8样例输出1
NO样例输出2
YES数据范围
对于全部数据，1≤F≤5,1≤N≤500,1≤M≤2500,1≤W≤200,1≤S,E≤N,|T|≤10^4。
解题报告
这道题目要求我们判断John是否可以通过虫洞回到过去。我们可以将这个问题转化为图论中的最短路径问题。具体来说，我们需要判断是否存在一个负权环。如果存在负权环，那么John就可以通过虫洞回到过去。
我们可以使用SPFA（Shortest Path Faster Algorithm）算法来解决这个问题。SPFA是一种改进的Bellman-Ford算法，适用于求解带有负权边的最短路径问题。SPFA算法的基本思想是通过队列来维护待处理的节点，并且通过松弛操作来更新最短路径。
标准程序
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,w,i,x,y,z,dis[N],vis[N],fl[N];
vector <int> f[N],g[N];
queue <int> q;
void spfa(int x){
int fx,sx,sg,i;
dis[x]=0;vis[x]=1;q.push(x);
while(!q.empty()){
fx=q.front();q.pop();
vis[fx]=0;fl[fx]++;
if(fl[fx]>n) cout<<"YES",exit(0);
for(i=0;i<f[fx].size();i++){
sx=f[fx][i];sg=g[fx][i];
if(sg+dis[fx]<dis[sx]){
dis[sx]=sg+dis[fx];
if(vis[sx]==0) q.push(sx),vis[sx]=1;
}
}
}
}
int main(){
cin>>n>>m>>w;
for(i=1;i<=m;i++) cin>>x>>y>>z,
f[x].push_back(y),f[y].push_back(x),
g[x].push_back(z),g[y].push_back(z);
for(i=1;i<=w;i++) cin>>x>>y>>z,
f[x].push_back(y),g[x].push_back(-z);
for(i=1;i<=n;i++) dis[i]=1e9;
for(i=1;i<=n;i++) if(fl[i]==0) spfa(i);
cout<<"NO";
}P2：单词戒指WordRings
题目描述
题目描述
我们有 n 个字符串，每个字符串都是由 a 至 z 的小写英文字母组成的。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。如下例：
ababc
bckjaca
caahoynaab第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 5+7+10=22（重复部分算两次），总共使用了 3 个串，所以平均长度是 223≈7.33。
输入
每组数据的第一行，一个整数 n，表示字符串数量；
接下来 n 行，每行一个长度小于等于 1000 的字符串。
输出
若不存在环串，输出 No solution，否则输出最长的环串的平均长度。
只要答案与标准答案的差不超过 0.01，就视为答案正确。
样例输入
3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein样例输出
21.67数据范围
对于全部数据，1≤n≤10^5 。
解题报告
这道题要求我们找到一个环串，使得环串的平均长度最大。我们可以使用动态规划来解决这个问题。
我们定义 fi 表示以第 i 个字符串结尾，第 j 个字符串开头的最长环串的长度。我们可以枚举第 i 个字符串的结尾和第 j 个字符串的开头，然后判断它们是否能够相连。如果能够相连，我们就可以更新 fi 的值。
有一定的哈希思路
标准程序
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int i,j,l,n,x,y,fx,sx,vis[N],fl[N],f[N][N];
double t,w,bao,mid,sg,dis[N];
char s[N];
queue <int> q;
vector <int> h[N],g[N];
int haha(char a,char b){return (a-97)*26+(b-97);}
bool spfa(int x,double s){
int i;
q.push(x);dis[x]=0;vis[x]=1;
while(!q.empty()){
fx=q.front();q.pop();
vis[fx]=0;fl[fx]++;
if(fl[fx]>haha('z','z')) return 1;
for(i=0;i<h[fx].size();i++){
sx=h[fx][i];sg=g[fx][i]-s;
if(dis[fx]+sg>dis[sx]){
dis[sx]=sg+dis[fx];
if(vis[sx]==0) q.push(sx),vis[sx]=1;
}
}
}
return 0;
}
bool pd(double x){
int i;
for(i=0;i<=haha('z','z');i++) dis[i]=-1e9,vis[i]=fl[i]=0;
for(i=0;i<=haha('z','z');i++) if(fl[i]==0&&spfa(i,x)) return 1;
return 0;
}
int main(){
cin>>n;
for(i=1;i<=n;i++){
cin>>s+1;l=strlen(s+1);
x=haha(s[1],s[2]);y=haha(s[l-1],s[l]);
f[x][y]=max(f[x][y],l);
}
for(i=0;i<=haha('z','z');i++) for(j=0;j<=haha('z','z');j++)
if(f[i][j]>0) h[i].push_back(j),g[i].push_back(f[i][j]);
t=0;w=1000;bao=-1;
while(w-t>1e-6){
mid=(t+w)/2;
if(pd(mid)) bao=mid,t=mid+1e-6;
else w=mid-1e-6;
}
if(bao==-1) cout<<"No solution";
else printf("%.2lf",bao);
}
