poj 3621最优比例生成环（01分数规划问题）

/*

和求最小生成树差不多

转载思路：http://www.cnblogs.com/wally/p/3228171.html

思路：之前做过最小比率生成树，也是属于0/1整数划分问题，这次碰到这道最优比率环，很是熟悉，可惜精度没控制好，要不就是wa,要不就是tle，郁闷啊！实在是懒得码字，直接copy吧：

题目的意思是：求一个环的{点权和}除以{边权和}，使得那个环在所有环中{点权和}除以{边权和}最大。

令在一个环里，点权为v[i]，对应的边权为e[i]，

即要求：∑（i=1，n）v[i]/∑（i=1，n)e[i]最大的环（n为环的点数），

设题目答案为ans，

即对于所有的环都有 ∑（i=1，n）（v[i]）/∑（i=1，n)（e[i]）<=ans

变形得ans* ∑（i=1，n）（e[i]）>=∑（i=1，n）（v[i]）

再得 ∑（i=1，n）（ans*e[i]-v[i]） >=0

稍分析一下，就有：

当k<ans时，就存在至少一个环∑（i=1，n）（k*e[i]-v[i]）<0，即有负权回路(边权为k*e[i]-v[i])；

当k>=ans时，就对于所有的环∑（i=1，n）（k*e[i]-v[i]）>=0，即没有负权回路。

然后我们就可以使新的边权为k*e[i]-v[i]，用spfa来判断付权回路,二分ans。

*/

#include<stdio.h>

#include<string.h>

#include<queue>

#include<stdlib.h>

using namespace std;

#define N 1100

#define eps  1e-3

#define inf 0x3fffffff

struct node {

  int u,v,w,next;

}bian[N*5*2];

int head[N],yong,f[N],n;

void init() {

yong=0;

memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int w) {

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

int spfa(double  m) {

 queue<int>q;

 int vis[N],v,cou[N];

 double dis[N];

 int i;

 memset(vis,0,sizeof(vis));

 memset(cou,0,sizeof(cou));

 for(i=1;i<=n;i++)

    dis[i]=inf;

 dis[1]=0;

 cou[1]++;

 q.push(1);

 while(!q.empty()) {

    v=q.front();

    q.pop();

    vis[v]=0;

    for(i=head[v];i!=-1;i=bian[i].next) {

            int vv=bian[i].v;

        double tmp=m*bian[i].w-f[vv];//构造新边

        if(dis[v]+tmp<dis[vv]){

            dis[vv]=dis[v]+tmp;

            if(!vis[vv]) {

            vis[vv]=1;

            if(++cou[vv]>n)//

                return 1;

    q.push(vv);

            }

        }

    }

 }

 return 0;

}

int main(){

     int m,i,a,b,c;

     while(scanf("%d%d",&n,&m)!=EOF) {

        init();

        for(i=1;i<=n;i++)

            scanf("%d",&f[i]);

        while(m--) {

            scanf("%d%d%d",&a,&b,&c);

            addedge(a,b,c);

        }

        double l=0.0,r=10000.0,ans=0,mid;

        while(r-l>eps) {//结束条件为l>r

            mid=(r+l)/2;

            if(spfa(mid)) {

             ans=mid;

                l=mid+0.00001;

            }

            else

                r=mid-0.00001;

        }

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

     }

return 0;

}
巴特西

poj 3621最优比例生成环（01分数规划问题）

最新文章

热门文章
