bzoj3597方伯伯运椰子

bzoj3597方伯伯运椰子

.php?id=3597

运呀运呀运椰子QAQ

听说是分数规划，然后就先去学了一发，顺便水了一发poj2728.

（先吐槽：马丹，题面好长啊）

然后，贴上分析历程：

每条边u->v建立 bi+di表示往这边多跑一次流量和运费都增加          最多inf 
反向建立v->u ai-di表示少跑一次需要花费(压缩花ai,不跑送回来di)ai-di  最多c 
然后，如果当前存在负权环，说明还可以更优，在负权环上跑一次残量网络可以得到更优的费用
这里的费用都是变化的费用,并且费用为负，使得费用/（环长*流量）最小  
然后对于同一个环，这个比值是一定的，所以不妨把流量都看做1


然后题目就变成了求费用/环长最小          费用为负
==求平均值最小的负权环 
按照01规划思想


考虑r=∑xi*wi/∑xi*1            ->     z=∑xi*wi-r'∑xi*1 =∑xi(wi-r')   二分枚举这个 r'使得z=0
要注意r'是负的，我们可以枚举-r'=r''       当z<0时,r'>r    -r''>r    r''<-r    r''需要更大 l=mid
也就是找到负权环z<=0 l=mid     否则r=mid. 

然后跑spfa找是否存在负环。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
/*
每条边u->v建立 bi+di表示往这边多跑一次流量和运费都增加          最多inf 
反向建立v->u ai-di表示少跑一次需要花费(压缩花ai,不跑送回来di)ai-di  最多c 
然后，如果当前存在负权环，说明还可以更优，在负权环上跑一次残量网络可以得到更优的费用
这里的费用都是变化的费用,并且费用为负，使得费用/（环长*流量）最小  
然后对于同一个环，这个比值是一定的，所以不妨把流量都看做1然后题目就变成了求费用/环长最小          费用为负
==求平均值最小的负权环 
按照01规划思想考虑r=∑xi*wi/∑xi*1            ->     z=∑xi*wi-r'∑xi*1 =∑xi(wi-r')   二分枚举这个 r'使得z=0
要注意r'是负的，我们可以枚举-r'=r''       当z<0时,r'>r    -r''>r    r''<-r    r''需要更大 l=mid
也就是找到负权环z<=0 l=mid     否则r=mid. 
*/
const int maxn=3020;
int n,m;
struct edge
{int v,next;double w;
}e[maxn*2];
int head[5020];
int inq[maxn];
double dis[maxn];
int cnt;
void add(int u,int v,double w)
{e[cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt++;
}
bool spfa(int u)
{inq[u]=1;for(int i=head[u];~i;i=e[i].next){int v=e[i].v;if(dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;if(inq[v])return true;if(spfa(v))return true;}}inq[u]=0;return false;
}
bool work()
{for(int i=1;i<=n+2;i++){dis[i]=0;inq[i]=0;}for(int i=1;i<=n+2;i++){if(spfa(i))return true;}return false;
}
int main()
{memset(head,-1,sizeof(head));cnt=0;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,a,b,c,d;scanf("%d%d%d%d%d%d",&u,&v,&a,&b,&c,&d);add(u,v,b+d);if(c>0)add(v,u,a-d);}double l=0,r=1e9;while(r-l>1e-4){double mid=(l+r)/2;for(int i=0;i<cnt;i++)e[i].w+=mid;if(work())l=mid;else r=mid;for(int i=0;i<cnt;i++)e[i].w-=mid;}printf("%.2fn",l);return 0;
}