NOIP 2016 提高組 Day 1 第三題 換教室

瘋狂的函數 2022-01-07 20:35:45 阅读数:524

noip 提高 day 第三 教室

題目描述

對於剛上大學的牛牛來說,他面臨的第一個問題是如何根據實際情况申請合適的課程。

在可以選擇的課程中,有2n節課程安排在n個時間段上。在第i (1 <= i <= n)個時間段上,兩節內容相同的課程同時在不同的地點進行,其中,牛牛預先被安排在教室ci上課,而另一節課程在教室di進行。

在不提交任何申請的情况下,學生們需要按時間段的順序依次完成所有的n節安排好的課程。如果學生想更換第i節課程的教室,則需要提出申請。若申請通過,學生就可以在第i個時間段去教室di上課,否則仍然在教室ci上課。

由於更換教室的需求太多,申請不一定能獲得通過。通過計算,牛牛發現申請更換第i節課程的教室時,申請被通過的概率是一個已知的實數ki,並且對於不同課程的申請,被通過的概率是互相獨立的。

學校規定,所有的申請只能在學期開始前一次性提交,並且每個人只能選擇至多m節課程進行申請。這意味著牛牛必須一次性决定是否申請更換每節課的教室,而不能根據某些課程的申請結果來决定其他課程是否申請;牛牛可以申請自己最希望更換教室的m門課程,也可以 不用完 這m個申請的機會,甚至可以一門課程都不申請。

因為不同的課程可能會被安排在不同的教室進行,所以牛牛需要利用課間時間從一間教室趕到另一間教室。

牛牛所在的大學有v個教室,有e條道路。每條道路連接兩間教室,並且是可以 雙向通行 的。由於道路的長度和擁堵程度不同,通過不同的道路耗費的體力可能會有所不同。當第i (1<= i <= n-1)節課結束後,牛牛就會從這節課的教室出發,選擇一條耗費體力最少的 路徑 前往下一節課的教室。

現在牛牛想知道,申請哪幾門課程可以使他因在教室間移動耗費的體力值的總和的 期望值 最小,請你幫他求出這個最小值。

輸入

第一行四個整數n, m, v, e。n錶示這個學期內的時間段的數量;m錶示牛牛最多可以申請更換多少節課程的教室;v錶示牛牛學校裏教室的數量;e錶示牛牛的學校裏道路的數量。

第二行n個正整數,第i (1 <= i<= n)個正整數錶示ci,即第i個時間段牛牛被安排上課的教室;保證1 <= Ci <= v。

第三行n個正整數,第i (1<=i<=n)個正整數錶示di,即第i個時間段另一間上同樣課程的教室;保證1<=di<=v。

第四行n個實數,第i (1<=i<=n)個實數錶示ki,即牛牛申請在第i個時間段更換教室獲得通過的概率。保證0 <= ki <= 1。

接下來e行,每行三個正整數aj,bj,wj,錶示有一條雙向道路連接教室aj,bj,通過這條道路需要耗費的體力值是wj;保證1 <= aj, bj <= v, 1 <= wj <= 100。

保證 1 <= n <= 2000,0 <= m <= 2000, 1 <= v <= 300, 0 <= e <= 90000。

保證通過學校裏的道路,從任何一間教室出發,都能到達其他所有的教室。

保證輸入的實數最多包含3比特小數。

輸出

輸出一行,包含一個實數,四舍五入精確到小數點後 恰好2比特 ,錶示答案。你的輸出必須和標准輸出 完全一樣 才算正確。

測試數據保證四舍五入後的答案和准確答案的差的絕對值不大於4 x 10^-3。(如果你不知道什麼是浮點誤差,這段話可以理解為:對於大多數的算法,你可以正常地使用浮點數類型而不用對它進行特殊的處理)

樣例輸入

3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1

樣例輸出

2.80

提示

【樣例1說明】

所有可行的申請方案和期望收益如下錶:

【提示】

  1. 道路中可能會有多條雙向道路連接相同的兩間教室。也有可能有道路兩端連接的是 同一間 教室。
  2. 請注意區分n,m,v,e的意義,n 不是 教室的數量,m 不是 道路的數量。 

【子任務】

特殊性質1:圖上任意兩點ai , bi , ai ≠ bi間,存在一條耗費體力最少的路徑只包含一條道路。
特殊性質2:對於所有的1 <= i <= n,ki = 1。

程序實現

#include <bits/stdc++.h>
using namespace std;
#define lson(u) (u<<1)
#define rson(u) (u<<1|1)
#define Pi acos(-1)
#define iINF 0x3f3f3f3f
#define lINF 0x3f3f3f3f3f3f3f
#define EPS 0.000000001
#define pii pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
const int MAXN1=2005;
const int MAXN2=305;
const ll Mod=1e9+7;
int n,m,v,e;
int C[MAXN1],D[MAXN1];
double K[MAXN1],f[MAXN1][MAXN1][2],dis[MAXN2][MAXN2];
void floyd()
{
for(int k=1;k<=v;k++)
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
}
void Init()
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
{
dis[i][j]=iINF;
}
}
for(int i=1;i<=v;i++)
{
dis[i][i] = 0;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j][0]=f[i][j][1]=iINF;
}
}
}
int main()
{
int x,y,xy;
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=n;i++)
{
scanf("%d",&C[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&D[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%lf",&K[i]);
}
Init();
for(int i=0;i<e;i++)
{
scanf("%d%d%d",&x,&y,&xy);
dis[x][y]=min(dis[x][y],double(xy));
dis[y][x]=min(dis[y][x],double(xy));
}
floyd();
double dis1,dis2;
double ans=iINF;
f[1][0][0]=f[1][1][1]=0;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=m&&j<=i;j++)
{
dis1=dis[C[i]][C[i-1]];
dis2=dis[C[i]][D[i-1]]*K[i-1] + dis[C[i]][C[i-1]]*(1.0-K[i-1]);
if(j==0)
{
f[i][j][0]=f[i-1][j][0]+dis1;
}
else
{
f[i][j][0] = min(f[i-1][j][0] + dis1, f[i-1][j][1] + dis2);
}
if(j == 0)
{
continue;
}
dis1=dis[D[i]][C[i-1]]*K[i]+dis[C[i]][C[i-1]]*(1.0-K[i]);
dis2=dis[D[i]][D[i-1]]*K[i]*K[i-1]+dis[D[i]][C[i-1]]*K[i]*(1.0-K[i-1])+dis[C[i]][D[i-1]]*(1.0-K[i])*K[i-1]+dis[C[i]][C[i-1]]*(1.0-K[i])*(1.0-K[i-1]);
f[i][j][1]=min(f[i-1][j-1][0]+dis1,f[i-1][j-1][1]+dis2);
}
}
for(int j=0;j<=m&&j<=n;j++) {
ans=min(ans,f[n][j][0]);
ans=min(ans,f[n][j][1]);
}
printf("%0.2lf",ans);
return 0;
}
版权声明:本文为[瘋狂的函數]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072035449945.html