題目描述：
有N個串，兩個尾首兩個字母相同的串可以連接。求最大均值圈。
算法分析：
建圖以后，二分枚舉結果，判斷是否有正環。
正環的話按照深搜版spfa求。
pku2949
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int V = 26*26;
6 const int E = (int)1e5+5;
7 int pnt[E] ,head[V], nxt[E],e, cost[E],stk[V],n,vis[V];
8 double d, dp[V];
9 // find circle
10 int flag ;
11 inline bool chkmax(double &a,const double b){
12 if(a<b){a = b; return 1;} else return 0;
13 }
14 void dfs(int u){
15 //cout<<"u: "<<u<<endl;
16 stk[u] = 1;
17 for(int i = head[u]; i !=-1 ; i = nxt[i]){
18 int v = pnt[i];
19 if(chkmax(dp[v], dp[u] + cost[i] - d)){
20 if(stk[v]){
21 flag = 1; return ;
22 }
23 else
24 dfs(v); if(flag) return ;}
25 }
26 stk[u] = 0;
27 }
28 inline bool judge(double val){
29 d = val; flag = 0;
30 memset(stk,0,sizeof(stk));
31 for(int i = 0; i < n; i++) dp[i] = 0;
32 for(int i = 0; i < n; i++){
33 //for(int j = 0; j < n; j++) dp[j] = 0;
34 dfs(i);
35 if(flag) return 1;
36 }
37 return 0;
38 }
39 // graph
40 int hash[V];
41 int find(int val){
42 if(hash[val] == -1){
43 hash[val] = n++;
44 return n - 1;
45 }
46 else return hash[val];
47 }
48 void add(int u,int v,int c){
49 nxt[e] = head[u]; head[u] = e; pnt[e] = v; cost[e++] = c;
50 }
51 char ch[1005];
52 double fix(double l){
53 return int(l*100+1e-9)/100.0;
54 }
55 // judge circle
56 bool judge(int u){
57 vis[u] = 1;
58 for(int i = head[u]; i!=-1; i=nxt[i]) {
59 int v = pnt[i];
60 if(vis[v] == 1) return 1;
61 else if(judge(v)) return 1;
62 }
63 return 0;
64 }
65 int main(){
66 int m;
67 while(scanf("%d",&m) ,m){
68 e = n = 0;
69 memset(hash,-1,sizeof(hash));
70 memset(head,-1,sizeof(head));
71 memset(vis,0,sizeof(vis));
72 for(int i = 0; i < m; i++){
73 scanf("%s",ch);
74 int l = strlen(ch);
75 int u = (ch[0] - 'a') * 26 + (ch[1] - 'a');
76 int v = (ch[l-2] - 'a') * 26 + (ch[l-1] - 'a');
77 u = find(u);
78 v = find(v);
79 add(u,v,l);
80 }
81 bool circle = 0;
82 for(int i = 0; i < n; i++){
83 if(!vis[i] && judge(i)){circle = 1; break;}
84 }
85 if(circle == 0) {puts("No solution."); continue;}
86 double l = 0, r = 1000, ans;
87 for(int i = 0; i < 500; i++){
88 double m = (l+r)/2;
89 // cout<<l<<" "<<r<<" m: "<<m<<endl;
90 if(judge(m)) l = m; else {ans = r = m;}
91 }
92 printf("%.2lf\n",fix(ans));
93 }
94 }
95
96 posted on 2012-10-10 19:32
西月弦 閱讀(306)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告