社区讨论
补充一组数据。
P2538[SCOI2008] 城堡参与者 5已保存回复 16
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 16 条
- 当前快照
- 1 份
- 快照标识符
- @mi7ydhv7
- 此快照首次捕获于
- 2025/11/21 05:38 4 个月前
- 此快照最后确认于
- 2025/11/21 06:42 4 个月前
chen_zhe
yjjr
CPP50 0 3
40 7 9 44 15 20 44 10 21 12 30 45 19 9 10 24 0 19 43 45 10 23 20 2 25 22 3 10 26 5 34 14 39 23 33 20 35 7 37 18 31 34 43 11 46 42 8 24 20 30
27356 11619 29477 2896 4657 11350 15037 32117 7733 10537 2274 20334 21589 24300 19058 8301 25992 20229 32334 10915 16074 8147 10601 14085 15820 20114 20766 32336 7658 14463 28615 6986 12637 16188 6027 29259 15026 3189 14199 12797 31354 14532 14032 20832 17732 22994 23208 12049 13768 15296
答案应该是94625,第一,二篇均输出110355。
选择的城堡(一种方案)应该是4,15,12。
已经确保这样的方案可以保证每个城市都至少有一个城堡能够到达。
附上我的代码:
CPP选择的城堡(一种方案)应该是4,15,12。
已经确保这样的方案可以保证每个城市都至少有一个城堡能够到达。
附上我的代码:
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=55;
int dis[N][N],a[N];
bool f[N];
int n,m,K,b[N],dp[N],Dp[N],cnt;
inline int solve(){
memcpy(dp,Dp,(n+1)<<2);
static int i,j,ans;
for(i=1;i<=K;++i)
for(j=1;j<=n;++j)
dp[j]=min(dp[j],dis[b[i]][j]);
ans=0;
// for(i=1;i<=n;++i)printf("%d ",dp[i]);
for(i=1;i<=n;++i)ans=max(ans,dp[i]);
return ans;
}inline void work(){random_shuffle(b+1,b+1+cnt);}
inline double get_double(){return rand()*1.0/RAND_MAX;}
int main(){
// freopen("0.in","r",stdin);
srand(time(NULL));
memset(Dp,0x7f,sizeof(Dp));
memset(dis,0x3f,sizeof(dis));
int i,j,k;
scanf("%d%d%d",&n,&m,&K);
for(i=1;i<=n;++i)scanf("%d",&a[i]),++a[i];
int x;
for(i=1;i<=n;++i){
dis[i][i]=0;
scanf("%d",&x);
dis[i][a[i]]=dis[a[i]][i]=min(dis[i][a[i]],x);
}for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
dis[j][k]=min(dis[j][i]+dis[i][k],dis[j][k]);
for(i=1;i<=m;++i)scanf("%d",&x),f[++x]=1;
for(i=1;i<=n;++i)
if(!f[i])b[++cnt]=i;
else
for(j=1;j<=n;++j)
Dp[j]=min(Dp[j],dis[i][j]);
work();
// b[1]=4,b[2]=15,b[3]=12;
int ans=solve();
int T=5,G;
int pre;
while(T--){
work();
ans=min(ans,solve());
G=20;
while(G--){
for(i=K+1;i<=cnt;++i)
for(j=1;j<=K;++j){
swap(b[i],b[j]);
pre=ans;
ans=solve();
if(pre<ans){
ans=pre;
swap(b[i],b[j]);
}
}
}
}printf("%d\n",ans);
return 0;
}
此代码已通过此题。
回复
共 16 条回复,欢迎继续交流。
正在加载回复...