poj 2049（二分+spfa判負環）

poj 2049（二分+spfa判負環）

給你一堆字符串，若字符串x的后兩個字符和y的前兩個字符相連，那么x可向y連邊。問字符串環的平均最小值是多少。1 ≤ n ≤ 100000，有多組數據。

首先根據套路，二分是顯然的。然后跑一下spfa判斷正環就行了。

然而我被no solution坑了十次提交。。

#include <cctype>
#include <cstdio>
#include <cstring>
using namespace std;const int maxn=1e5+5, maxm=1e5+5;
const double eps=1e-4;struct Graph{struct Edge{int to, next, v; Graph *bel;inline int operator *(){ return to; }Edge& operator ++(){return *this=bel->edge[next]; }};void reset(){cntedge=0; memset(fir, 0, sizeof(fir)); }void addedge(int x, int y, int v){Edge &e=edge[++cntedge];e.to=y; e.next=fir[x]; e.v=v;e.bel=this; fir[x]=cntedge;}Edge& getlink(int x){ return edge[fir[x]]; }//Edge edge[maxm*2];int cntedge, fir[maxn];
}g;int n, len, visit[maxn];
double dis[maxn], l, r, mid; bool flag;
char s[1005];int trans(char c1, char c2){return (c1-'a')*26+c2-'a'+1; }bool spfa(int now, double A){Graph::Edge e=g.getlink(now); visit[now]=1;for (; *e; ++e){if (dis[now]+A-e.v<dis[*e]){dis[*e]=dis[now]+A-e.v;if (visit[*e]||spfa(*e, A)) return true;}} visit[now]=0;return false;
}int main(){for (; scanf("%d", &n), n; ){g.reset();for (int i=1; i<=n; ++i){do{fgets(s, 1e5, stdin);len=strlen(s);}while (len<2);g.addedge(trans(s[0], s[1]),trans(s[len-3], s[len-2]), len-1);}l=0; r=2000;while (r-l>eps){mid=(l+r)/2; flag=false;for (int i=1; i<=26*26; ++i) dis[i]=visit[i]=0;for (int i=1; i<=26*26; ++i)if (spfa(i, mid)){ flag=true; break; }if (flag) l=mid; else r=mid;}if (r<=eps) printf("No solution.\n");else printf("%.3lf\n", (l+r)/2);}return 0;
}