bzoj 1690: [Usaco2007 Dec]奶牛的旅行

本文主要是介绍bzoj 1690: [Usaco2007 Dec]奶牛的旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1690

思路：0-1分数规划

其实0-1分数规划重要的是它的思想，就像最小乘积XXX（生成树，匹配等）一样，知道了思想，再套一个对应的的算法即可

一个不错的博客：http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html

说下我的理解：

首先0-1分数规划是用来解决这一类问题：

有N个东西，可以选或不选（用0,1来表示），选了有A[i]的收益，但要付出B[i]的代价

最后求一种方案使得(ΣA[i])/(ΣB[i])最大（或最小）

形式上和最小乘积XXX很像，就是乘号改成除号

但是解决方法却很不同

首先我们用x[i]取1或0表示i是选还是不选（如果x[i]的取值不限制在0，1中就是更一般的分数规划了）

先讨论最大的情况，最小类似

那么假设最优解为R=Σ(A[i]*x[i])/Σ(B[i]*x[i])

移项Σ(A[i]*x[i])-R*Σ(B[i]*x[i])=0

构造一个新函数f(L)=Σ(A[i]*x[i])-L*Σ(B[i]*x[i])

合并同类项令d[i]=Σ((A[i]-L*B[i])*x[i])

f(L)=Σ(d[i]*x[i])

如果有一个方案X使得f(L)>0，

那么Σ(A[i]*x[i])/Σ(B[i]*x[i])>L

这说明这个方案的值比L更大，那我们就选它

d数组是随L单调减的，所以任何一种方案，L减小，f(L)都会下降，所以这个函数就有了单调性

于是我们就可以二分了

这题就是求最优比例环

首先不会有环套环，这个随便证一下就可以了

每次二分L，把边权赋成d[i]，把收益也转到边上，判断是否存在正权环即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=1010,maxm=5010;
const double eps=1e-5;
using namespace std;
int n,m,v[maxn],pre[maxm],now[maxn],son[maxm],val[maxm],tot;double ans=0.0,mid,dis[maxn];bool vis[maxn];
void add(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}int spfa(int x){vis[x]=1;for (int y=now[x];y;y=pre[y]){double nval=v[son[y]]-mid*val[y];if (dis[son[y]]<dis[x]+nval){if (!vis[son[y]]){dis[son[y]]=dis[x]+nval;if (spfa(son[y])) return 1;}else return 1;}}return vis[x]=0;
}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&v[i]);for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z);double l=0.0,r=1000.0;mid=(l+r)/2.0;while (r-l>eps){memset(dis,254,sizeof(dis));memset(vis,0,sizeof(vis));dis[1]=0.0;if (spfa(1)) ans=mid,l=mid;else r=mid;//printf("%.2f %.2f\n",l,r);mid=(l+r)/2.0;}printf("%.2f\n",ans);return 0;
}