图论&数学：最小平均值环

POJ2989：求解最小平均值环

最优化平均值的显然做法是01分数规划

给定一个带权有向图

对于这个图中的每一个环

定义这个环的价值为权值之和的平均值

对于所有的环，求出最小的平均值

这个结论怎么做的我找不到，但是显然的做法是可以找到的

由于Average=(E1+E2+…..+Ek)/K

所以Average*K=E1+E2+……+Ek

即（E1-Average）+（E2-Average）+….+ （Ek-Average）=

另外注意到上式中的等于号可以改写为小于等于，那么我们可以二分答案Ans，然后判断是否存在一组解满足（E1+E2+…..+Ek）/K>Ans,即判断

（E1- Ans）+（E2- Ans）+….+ （Ek- Ans）>

于是在二分答案后，我们把边的权值更新，问题就变成了查找图中是否存在一个正环

也就是二分答案+spfa判断正环

然后学到了，DFS的SPFA判环贼快

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define ll long long

 #define inf 0x3f3f3f3f

 #define N 700

 #define M 100010

 #define eps 1e-4

 inline int read(){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

     return x*f;

 }

 int n,h[N],num;

 double d[N];

 char s[];

 bool vis[N];

 struct edge{

     int to,next,val;

 }data[M];

 inline void add(int x,int y,int val){

     data[++num].to=y;data[num].next=h[x];h[x]=num;data[num].val=val;

 }

 inline int calc(char a,char b){return (a-'a')*+b-'a'+;}

 bool dfs(int x,double mid){//判正环

     vis[x]=;

     for(int i=h[x];i;i=data[i].next){

         int y=data[i].to;

         if(d[x]+data[i].val-mid>d[y]){

             d[y]=d[x]+data[i].val-mid;

             if(vis[y]||dfs(y,mid)){vis[x]=;return ;}

         }

     }vis[x]=;return ;

 }

 inline bool jud(double mid){

     memset(d,,sizeof(d));

     for(int i=;i<=*;++i) if(dfs(i,mid)) return ;

     return ;

 }

 int main(){

 //  freopen("a.in","r",stdin);

     while(){

         n=read();if(!n) break;num=;memset(h,,sizeof(h));

         while(n--){

             scanf("%s",s+);int len=strlen(s+);

             add(calc(s[],s[]),calc(s[len-],s[len]),len);

         }

         double l=,r=;

         while(r-l>=eps){

             double mid=(r+l)/;

             if(jud(mid)) l=mid;

             else r=mid;

         }

         if(l==) puts("No solution.");

         else printf("%.2f\n",l);

     }

     return ;

 }