[bzoj1690] 奶牛的旅行 （最大比率環）
題目
作為對奶牛們辛勤工作的回報，Farmer John決定帶她們去附近的大城市玩一天。旅行的前夜，奶牛們在興奮地討論如何最好地享受這難得的閑暇。 很幸運地，奶牛們找到了一張詳細的城市地圖，上面標註了城市中所有L(2 <= L <= 1000)座標誌性建築物（建築物按1..L順次編號），以及連接這些建築物的P(2 <= P <= 5000)條道路。按照計劃，那天早上Farmer John會開車將奶牛們送到某個她們指定的建築物旁邊，等奶牛們完成她們的整個旅行並回到出發點後，將她們接回農場。由於大城市中總是寸土寸金，所有的道路都很窄，政府不得不把它們都設定為通行方向固定的單行道。 儘管參觀那些標誌性建築物的確很有意思，但如果你認為奶牛們同樣享受穿行於大城市的車流中的話，你就大錯特錯了。與參觀景點相反，奶牛們把走路定義為無趣且令她們厭煩的活動。對於編號為i的標誌性建築物，奶牛們清楚地知道參觀它能給自己帶來的樂趣值F_i (1 <= F_i <= 1000)。相對於奶牛們在走路上花的時間，她們參觀建築物的耗時可以忽略不計。 奶牛們同樣仔細地研究過城市中的道路。她們知道第i條道路兩端的建築物 L1_i和L2_i（道路方向為L1_i -> L2_i），以及她們從道路的一頭走到另一頭所需要的時間T_i(1 <= T_i <= 1000)。 為了最好地享受她們的休息日，奶牛們希望她們在一整天中平均每單位時間內獲得的樂趣值最大。當然咯，奶牛們不會願意把同一個建築物參觀兩遍，也就是說，雖然她們可以兩次經過同一個建築物，但她們的樂趣值只會增加一次。順便說一句，為了讓奶牛們得到一些鍛煉，Farmer John要求奶牛們參觀至少2個建築物。 請你寫個程式，幫奶牛們計算一下她們能得到的最大平均樂趣值。
題解
分數規劃+spfa
首先，可以確定的是答案一定是簡單環。
粗略的證明：如果存在一個複雜環，把它拆成兩個環，這兩個環不可能點權和/邊權和都小於複雜環的點權和/邊權和，而複雜環中點權只計算一次，因此答案更小。
所以只要找到一個比值最大的簡單環即可。這顯然是一個01分數規劃問題。
於是二分答案，把點權加到邊權上（好像這個套路很常見），使用Spfa判斷是否存在正環即可。
注意最好用dfs版的spfa，處理負環速度更快
程式碼
#include <iostream>
#include <cstdio>
#define N 10000
using namespace std;
int head[N],cnt,to[N],nxt[N],n,m;
double cost[N],dis[N],cost2[N];
bool vis[N];
void connect(int a,int b,double c)
{
to[++cnt]=b,cost[cnt]=c,nxt[cnt]=head[a],head[a]=cnt;
}
int val[N];
bool dfs(int id)
{
vis[id]=true;
for(int i=head[id];i;i=nxt[i])
{
double d=dis[id]+cost2[i];
if(d<=dis[to[i]]) continue;
if(vis[to[i]]) return true;
dis[to[i]]=d;
if(dfs(to[i])) return true;
}
vis[id]=false;
return false;
}
bool check(double mid)
{
for(int i=1;i<=cnt;i++) cost2[i]=(double)val[to[i]]-mid*cost[i];
for(int i=1;i<=n;i++) dis[i]=-10000000,vis[i]=false;
dis[1]=0;
return dfs(1);
}
int main()
{
int tot=0;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&val[i]),tot+=val[i];
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
connect(a,b,c);
}
double l=0,r=100;
while(r-l>0.001)
{
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.2f", l);
}
