• 售前

  • 售后

热门帖子
入门百科

洛谷P1828 [USACO3.2] 香甜的黄油 Sweet Butter

[复制链接]
木头哈喇子崭 显示全部楼层 发表于 2022-1-15 23:40:27 |阅读模式 打印 上一主题 下一主题
标题大意

标题链接
                               p                          p               p个牧场之间有                              c                          c               c条路,有                              n                          n               n只在差异牧场的奶牛(大概有多头奶牛在同一个牧场)要到一个牧场去,找到一个牧场使全部奶牛必要走的隔断最短
输入格式

第一活动三个整数                              n                      、                      p                      、                      c                          n、p、c               n、p、c。
第                              2                          2               2~                              n                      +                      1                          n+1               n+1活动奶牛地点的牧场。
第                              n                      +                      2                          n+2               n+2~                              n                      +                      c                      +                      1                          n+c+1               n+c+1行,每行3个整数                              a                      、                      b                      、                      d                          a、b、d               a、b、d,表现                              a                          a               a牧场到                              b                          b               b牧场之间有一条长度为                              d                          d               d的双向蹊径
解题思绪

如图
                               B                      、                      C                      、                      D                          B、C、D               B、C、D牧场各有一头奶牛,最优的方案是选择                              D                          D               D牧场。

不丢脸出,这是一个最短路题目,罗列一个牧场,再将每个牧场的奶牛数                                   ∗                              *                  ∗离罗列的这个牧场的最短路,末了找出与各个牧场隔断最短的牧场,就是得到的终极答案。
这题的                              n                          n               n范围最大到达了                              500                          500               500,正常环境下都不会想到Floyed做法,由于                              O                      (                               n                         3                              )                          O(n^3)               O(n3)的做法肯定会T,但由于蹊径是双向的,因此从                              a                          a               a牧场去到                              b                          b               b牧场的隔断与从                              b                          b               b牧场去到                              a                          a               a牧场的隔断是一样的,因此在第三层循环时                              j                          j               j只必要循环到                              i                          i               i,更新                              d                      i                               s                                   i                            ,                            j                                           dis_{i,j}               disi,j​时将                              d                      i                               s                                   j                            ,                            i                                           dis_{j,i}               disj,i​同时更新即可。
代码

[code]#includeusing namespace std;int n,m,c,dis[1005][1005],mc[1005];int main(){    ios::sync_with_stdio(0);    cin.tie(0);        memset(dis,0x3f,sizeof(dis));         for(int j=1;j>n>>m>>c;        for(int i=1;i>x;                mc[x]++;        }        for(int i=1;i>x>>y>>w;                dis[x][y]=dis[y][x]=w;        }        for(int k=1;k

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作