poj 2049（二分+spfa判負環(huán)）

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

首先根據(jù)套路，二分是顯然的。然后跑一下spfa判斷正環(huán)就行了。

然而我被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; }

轉(zhuǎn)載于:https://www.cnblogs.com/MyNameIsPc/p/7989251.html

總結(jié)

以上是生活随笔為你收集整理的poj 2049（二分+spfa判负环）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。