2 条题解
-
0
这是无优化的spfa，1秒勉强过：
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=700, M=1110000; double eps=1e-3; struct edge{int x, y, c, pre;}a[M];int alen, last[N]; void ins(int x, int y, int c){ alen++; a[alen] = edge{x, y, c, last[x]}; last[x] = alen;} int n, dd[N];double d[N]; bool v[N]; char s[1100]; bool check(double mid) { memset(d, 0, sizeof(d)); memset(v, false, sizeof(v)); memset(dd, 0, sizeof(dd)); deque<int> q; for(int i=1; i<=676; i++) q.push_back(i), v[i] = 1; while(!q.empty()) { int x=q.front(); q.pop_front(); v[x]=0; for(int k=last[x]; k; k=a[k].pre) { int y=a[k].y; if(d[y] < d[x] + a[k].c - mid) { d[y] = d[x] + a[k].c - mid; dd[y] = dd[x] + 1; if(dd[y] >676) return true; if(v[y]==0) q.push_back(y), v[y] = 1; } } } return false; } int main() { freopen("i1.in", "r", stdin); int n; while(scanf("%d", &n), n) { alen=0; memset(last, 0, sizeof(last)); for(int i=1; i<=n; i++) { scanf("%s", s); int len=strlen(s); if(len >= 2) { int x=(s[0]-'a')*26 + (s[1]-'a') + 1; int y=(s[len-2]-'a')*26 + (s[len-1]-'a') + 1; ins(x, y, len); } } double l=0, r=1000, mid, ans=-1; while(l < r) { mid = (l + r)/2; if(check(mid)) l = mid + eps, ans = mid; else r = mid - eps; } if(ans != -1) printf("%.3lf\n", ans); else printf("No solution\n"); } return 0; }这是DFS优化的spfa，60毫秒，感觉有段没有必要学。：
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=27*27, M=1110000; double eps=1e-4; struct edge{int x, y, pre; double c;}a[M];int alen, last[N]; void ins(int x, int y, double c){ alen++; a[alen] = edge{x, y, last[x], c}; last[x] = alen;} int n, id[N], v[N]; double d[N], maxlen; char s[1100]; bool flag;//判断是否出现正环 void spfa(int x, int h, double len) { if(flag) return; for(int k=last[x]; k; k=a[k].pre) { int y=a[k].y; if(d[y] < d[x] + a[k].c - len) { d[y] = d[x] + a[k].c - len; if(d[y] > maxlen) { flag = true; return; } if(v[y] == 0) v[y] = h; spfa(y, h, len); if(flag) return; if(v[y] == h) { flag = true; return; } } } v[x] = 0; } bool check(double len) { flag = false; fill(d, d + n + 1, 0); fill(v, v + n + 1, 0); for(int i=1; i <= n; i++) { v[i] = i; spfa(i, i, len); if(flag) break; } return flag; } int main() { //freopen("i2.in", "r", stdin); int nn; while(scanf("%d", &nn), nn) { alen=0; memset(last, 0, sizeof(last)); memset(id, 0, sizeof(id)); maxlen=0; n=0; for(int i=1; i <= nn; i++) { scanf("%s", s); int len = double(strlen(s)); if(maxlen < len) maxlen = len; int x=(s[0]-'a')*26 + (s[1]-'a'); int y=(s[len-2]-'a')*26 + (s[len-1]-'a'); if(!id[x]) id[x] = ++n; if(!id[y]) id[y] = ++n; ins(id[x], id[y], double(len)); } maxlen *= nn; double l=0, r=1000, mid, ans=-1; while(l < r) { mid = (l + r)/2; if(check(mid)) l = mid + eps, ans = mid; else r = mid - eps; } if(ans != -1) printf("%.3lf\n", ans); else printf("No solution\n"); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:58:46
这是无优化的spfa，1秒勉强过：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=700,M=1110000; double eps=1e-3; struct edge{int x,y,c,pre;}a[M];int alen,last[N]; void ins(int x,int y,int c){ alen++;a[alen]=edge{x,y,c,last[x]};last[x]=alen;} int n,dd[N];double d[N]; bool v[N]; char s[1100]; bool check(double mid) { memset(d,0,sizeof(d));memset(v,False,sizeof(v)); memset(dd,0,sizeof(dd)); deque<int>q;for(int i=1;i<=676;i++)q.push_back(i),v[i]=1; while(!q.empty()) { int x=q.front();q.pop_front();v[x]=0; for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(d[y]<d[x]+a[k].c-mid) { d[y]=d[x]+a[k].c-mid; dd[y]=dd[x]+1;if(dd[y]>676) return True; if(v[y]==0) q.push_back(y),v[y]=1; } } } return False; } int main() { freopen("i1.in","r",stdin); int n;while(scanf("%d",&n),n){ alen=0;memset(last,0,sizeof(last)); for(int i=1;i<=n;i++) { scanf("%s",s); int len=strlen(s); if(len>=2) { int x=(s[0]-'a')*26+s[1]-'a'+1; int y=(s[len-2]-'a')*26+s[len-1]-'a'+1; ins(x,y,len); } } double l=0,r=1000,mid,ans=-1; while(l<r) { mid=(l+r)/2; if(check(mid))l=mid+eps,ans=mid; else r=mid-eps; } if(ans!=-1) printf("%.3lf\n",ans); else printf("No solution\n"); } return 0; }
这是DFS优化的spfa，60毫秒，感觉有段没有必要学。：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=27*27,M=1110000; double eps=1e-4; struct edge{int x,y,pre;double c;}a[M];int alen,last[N]; void ins(int x,int y,double c){ alen++;a[alen]=edge{x,y,last[x],c};last[x]=alen;} int n,id[N],v[N]; double d[N],maxlen; char s[1100]; bool flag;//判断是否出现正环 void spfa(int x,int h,double len) { if(flag) return; for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(d[y]<d[x]+a[k].c-len) { d[y]=d[x]+a[k].c-len; if(d[y]>maxlen) {flag=True;return ;} if(v[y]==0) v[y]=h,spfa(y,h,len); if(flag)return ; if(v[y]==h) { flag=True; return ; } } } v[x]=0; } bool check(double len) { flag=False; fill(d,d+n+1,0);fill(v,v+n+1,0); for(int i=1;i<=n;i++) { v[i]=i,spfa(i,i,len); if(flag) break; } return flag; } int main() { //freopen("i2.in","r",stdin); int nn;while(scanf("%d",&nn),nn){ alen=0;memset(last,0,sizeof(last)); memset(id,0,sizeof(id)); maxlen=0; n=0; for(int i=1;i<=nn;i++) { scanf("%s",s); int len=double(strlen(s));if(maxlen<len)maxlen=len; int x=(s[0]-'a')*26+s[1]-'a'; int y=(s[len-2]-'a')*26+s[len-1]-'a'; if(!id[x])id[x]=++n; if(!id[y])id[y]=++n; ins(id[x],id[y],double(len)); } maxlen*=nn; double l=0,r=1000,mid,ans=-1; while(l<r) { mid=(l+r)/2; if(check(mid))l=mid+eps,ans=mid; else r=mid-eps; } if(ans!=-1) printf("%.3lf\n",ans); else printf("No solution\n"); } return 0; }
- 1
