01整数规划

http://lghjx.573114.com/Blog/Html/103D/275536.html

下面的不是很清楚，这个比较好。

简介：

详情前参见国家集训队论文 2007年胡伯涛论文

题意:求存在一个环路,所有的点权之和/所以的边权之和最大是多少？

http://poj.org/problem?id=3621

算法:此题是对01分数规划的应用,那么首先明白01分数规划的思想.

01分数规划的思想的描述如下：令c=(c1,c2,…,cn)和d=(d1,d2,…,dn)为n维整数向量，那么一个0-1分数规划问题用公式描述如下:FP: 最小化(c1x1+…cnxn)/(d1x1…dnxn)=cx/dx xi∈{0,1}这里x表示列向量(x1,x2,…,xn)T .0-1值向量的子集Ω称作可行域，而x则是Ω的一个元素，我们称x为可行解。即可以简化为y=c/d.那么再演变一下：y-c/d=0.我们目标是求y.那么我们可以假设函数f(y)=y-c/d.

重要结论:

对于分数规划问题，有许多算法都能利用下面的线性目标函数解决问题。
Q(L): 最小化 cx-Ldx xi∈{0,1}

记z(L)为Q(L)的最值。令x*为分数规划的最优解，并且令L*=(cx*)/(dx*)(注：分数规划的最值)。那么下面就容易知道了：
z(L) > 0 当且仅当 L<L*
z(L) = 0 当且仅当 L=L*
z(L) < 0 当且仅当 L>L*
此外，Q(L*)的最优解也能使分数规划最优化。因此，解决分数规划问题在本质上等同于寻找L=L*使z(L)=0

因此,求解f(y)=0,为其函数的最优解，即可以利用二分的思想逐步推演y,从而求得最优解.

回到题目,我们知道是求解segma(f[V])/segma(E[v])的最大值,同时每个结点对应一个点权,每条边对应一个边权,那么我们就可以联想到应用01分数规划的思想来求解.而01分数规划是与二分紧紧联系在一起的.那么怎么应用二分求解呢？

我们首先想想当仅仅有2个结点环路的时候,问题就演变为f(y)=y-c/d,而y是通过二分逐步推算出来的,那么我们的任务就变为在一定的精度范围内测试求解其最优解.当y-c/d>0时,y减少; y-c/d<0时,y增大.在2个结点之间,那么我们就可用重新将图的权变为y-c/d,这样问题就回到2个结点的环路是否存在负权回路,存在说明y-c/d<0,不存在y-c/d>0.从而进一步推算最优解y。

/*
01整数规划问题，
01整数规划问题分为两类 最大化，最小化

以最小化如求最小值 l=ax/bx ，（ax bx是一些数的和），变形为 ax-l*bx=0,我们令 f(x)=min(ax-l*bx),我们要求的是这样的一个 l 对于给定的 l

首先 ax1-l*bx1=0

不存在 x 使得 (因为 l 是我们求的最小值)

ax-l*bx > 0

这样的话 ax>l*bx ;

关键是我们如何求这个l 呢? 有上面的我们可以得到，用二分法，求 l ，

对于 f(x)=min(ax-l*bx)

对于给定的 l

若 f(x)<0 则说明 l 偏大

若 f(x)>0 说明 l 偏小

对于图上的 01 整数规划我门只需要将边权变为 ax-l*bx 或者 l*bx- ax；

例如对于最优比率树：大意：给定一张图，每条边有一个收益值和一个花费值，求一个生成树，要求花费/收益最小，输出这个值

我们只需要将边权变为 a1-l*b1 然后求最小生成树就行判断求和的 ai-l*bi 的值于0 的大小

poj 2976 Dropping tests 【最优比例点】

http://poj.org/problem?id=2976

View Code

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<set>
 7 #include<map>
 8 #define Min(a,b)  a>b?b:a
 9 #define Max(a,b)  a>b?a:b
10 #define CL(a,num)  memset(a,num,sizeof(a));
11 #define inf 9999999
12 #define maxn 1030
13 #define eps  1e-6
14 
15 using namespace std;
16 int cmp(const double  a,const double  b)
17 {
18     return a>b;
19 }
20 double  a[maxn],b[maxn];
21 double d[maxn];
22 int main()
23 {
24     __int64 n,k,i;
25     while(scanf("%I64d%I64d",&n,&k),n+k)
26     {
27         for(i=1;i<=n;i++)
28          {
29              scanf("%lf",&a[i]);
30          }
31          for(i=1;i<=n;i++)scanf("%lf",&b[i]);
32          double l=0,r=-1;
33          for(i=1;i<=n;i++)
34          {
35              if(a[i]/(b[i]*1.0)>r)r = a[i]/(b[i]*1.0);
36          }
37 
38           int m=n-k;
39           double ans,mid;
40           r=100.0;
41          while(r-l>eps)
42          {
43              mid=(l+r)/2;
44              for(i=1;i<=n;i++)d[i]=a[i]*100.0-mid*b[i];
45              sort(d+1,d+n+1,cmp);
46 
47 
48 
49 
50              double temp=0;
51              for(i=1;i<=m;i++)temp+=d[i];
52              if(temp>=0)
53              {
54 
55 
56 
57 
58                  l=mid;
59 
60              }
61              else r=mid;
62          }
63 
64 
65          printf("%.0lf\n",mid);
66 
67     }
68 }

【例题2Poj2728Desert King——最优比率生成树】

http://poj.org/problem?id=2728

View Code

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<set>
  8 #include<map>
  9 #define Min(a,b)  a>b?b:a
 10 #define Max(a,b)  a>b?a:b
 11 #define CL(a,num)  memset(a,num,sizeof(a));
 12 #define inf 9999999
 13 #define maxn 1030
 14 #define eps  1e-6
 15 
 16 using namespace std;
 17 struct node
 18 {
 19     double x,y,h;
 20 }p[maxn];
 21 struct cnode
 22 {
 23     int k;
 24     double w;
 25     cnode(int kk,double ww): k(kk),w(ww){}
 26     friend bool operator < (cnode a,cnode b)
 27     {
 28         return a.w>b.w;
 29     }
 30 };
 31 int n;
 32 double mat[maxn][maxn],cost[maxn][maxn],dis[maxn],vis[maxn];
 33 priority_queue<cnode>que;
 34 void init()
 35 {
 36     int i,j;
 37     for(i=0;i<=n;i++)
 38     {
 39         for(j=0;j<=n;j++)
 40         {
 41             mat[i][j]=inf;
 42             cost[i][j]=0;
 43         }
 44     }
 45 }
 46 
 47 double  prim(double mid)
 48 {
 49     int i,j,k;
 50     double res=0;
 51     for(i=0;i<=n;i++)
 52     {
 53         dis[i]=inf;
 54         vis[i]=0;
 55     }
 56     dis[0]=0;
 57 
 58     for(i=0;i<n;i++)
 59     {
 60        double  min=inf;
 61         for(j=0;j<n;j++)
 62         {
 63             if(!vis[j]&&dis[j]<min)
 64             {
 65                 min=dis[j];
 66                 k=j;
 67             }
 68         }
 69         vis[k]=1;
 70         res+=dis[k];
 71         for(j=0;j<n;j++)
 72         {
 73             double t=cost[k][j]-mid*mat[k][j];
 74             if(!vis[j]&&mat[k][j]!=inf&&dis[j]>t)
 75             {
 76                 dis[j]=t;
 77             }
 78         }
 79 
 80     }
 81     return res;
 82 }
 83 int main()
 84 {
 85     int i,j;
 86     while(scanf("%d",&n),n)
 87     {
 88         for(i=0;i<n;i++)
 89         {
 90              scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].h);
 91         }
 92          init();
 93 
 94         double max=-1;
 95         for(i=0;i<n;i++)
 96           for(j=0;j<n;j++)
 97           {
 98               double l=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
 99               double w=fabs(p[i].h-p[j].h);
100               mat[i][j]=l;
101                mat[j][i]=l;
102               if(w>max)max=w;
103               cost[i][j]=w;
104               cost[j][i]=w;
105 
106           }
107 
108          double l=0,r=max,mid;
109          while(r-l>eps)
110          {
111              mid=(l+r)/2;
112              if(prim(mid) >= 0)
113              {
114 
115                  l = mid;
116              }
117              else r = mid;
118 
119          }
120          printf("%.3lf\n",mid);
121     }
122 
123 }

【例题3Poj3621Sightseeing Cows——最优比率环】

spfa （判负环）

http://poj.org/problem?id=3621

View Code

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<set>
 8 #include<map>
 9 #define Min(a,b)  a>b?b:a
10 #define Max(a,b)  a>b?a:b
11 #define CL(a,num)  memset(a,num,sizeof(a));
12 #define inf 9999999
13 #define maxn 1030
14 #define eps  1e-6
15 using namespace std;
16 struct node
17 {
18     int u;
19     int w;
20     node (int uu,int ww):u(uu),w(ww){}
21 };
22 vector<node>p[maxn];
23 int n,m;
24 queue<int>que;
25 double dis[maxn];
26 int vis[maxn],tol[maxn],a[maxn];
27 bool spfa(double mid)
28 {
29     int i;
30     while(!que.empty())que.pop();
31 
32 
33     for(i=1;i<=n;i++)que.push(i);
34 
35      for(i=1;i<=n;i++)
36        dis[i]=inf;
37 
38     CL(vis,true);  CL(tol,0);
39 
40     while(!que.empty())
41     {
42         int u=que.front();que.pop();
43         vis[u]=0;
44         for(i=0;i<p[u].size();i++)
45         {
46             node b=p[u][i];
47             int v=b.u;
48           double t = -a[v] + mid*b.w;
49           if(dis[v]>t+dis[u])
50           {
51                tol[v]++;
52               dis[v]=t+dis[u];
53               if(tol[v]>=n)return true;
54               if(!vis[v])
55               {
56                   vis[v]=1;
57                   que.push(v);
58               }
59 
60           }
61 
62         }
63     }
64     return false ;
65 }
66 int main()
67 {
68     int i,x,y,z;
69     while(scanf("%d%d",&n,&m)!=EOF)
70     {
71         for(i=1;i<=n;i++)scanf("%d",&a[i]);
72         for(i=0;i<=n;i++)p[i].clear();
73 
74 
75         while(m--)
76         {
77             scanf("%d%d%d",&x,&y,&z);
78             p[x].push_back(node(y,z));
79 
80         }
81         double l=0,r=2500,mid,ans=-1;
82         while(r-l>eps)
83         {
84             mid = (l+r)/2;
85             if(spfa(mid))
86             {
87                 ans=mid;
88                 l=mid;
89             }
90             else r=mid;
91         }
92         if(ans<-1)puts("0");
93         else printf("%.2lf\n",ans);
94 
95     }
96 }