首页 > 其他分享 >[USACO07NOV]牛继电器Cow Relays

[USACO07NOV]牛继电器Cow Relays

时间:2022-12-14 21:23:31浏览次数:72  
标签:Cow USACO07NOV edges min 矩阵 len floyd 条边 Relays

https://www.luogu.org/problem/P2886

题目描述:
给出一张无向连通图,求\(S\)到\(E\)经过\(k\)条边的最短路。

对于一类\(S\)到\(E\)走指定数量的边数,求它的最短路或条数,都可以采用矩阵快速幂的方式解决.我们回忆一下那一个慢得惊人的\(floyd\)算法,将它的\(dp\)方程式提取出来.

\(floyd[i][j]=min(floyd[i][k]+floyd[k][j])\)

如果我们把\(floyd\)看做一个矩阵,那么矩阵乘法的标准式则为:

\(floyd[i][j]=\sum_{i=1}^{n}(floyd[i][k]×floyd[k][j])\)

我们可以寻找这个方程的本质,可以发现,\((i,j)\)的路径条数可以利用加乘原理,化为\((i,k)×(k,j)\)的和,我们可以考虑这两个\(dp\)方程有什么相似之处.可以发现,上面的那个\(dp\)方程也可以用矩阵乘法的式子替代.我们可以将上面的\(dp\)式定义为矩阵\(min\).现在我们可以考虑k的存在,走\(k\)条边的状态可以由a条边的状态与\(k-a\)条边的状态转移过来,如果我们将走k条边的状态看做一个矩阵,则\(k\)条边的状态可以正好看做\(k\)个\(1\)矩阵相乘,并用矩阵快速“\(min\)"加速.矩阵\(min\)易证是满足结合律的.

原问题便转化为了求一个矩阵的\(k\)次"\(min\)".现在我们来考虑初始状态:当\(k\)=1时,就为邻接矩阵.

注意:矩阵“\(min\)"没有单位元.

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
   int map[201][201];
};
struct lisan
{
  int num,data,newdata;
  bool operator < (const lisan &a)const
  {
    return num<a.num;
  }
};
bool cmp(lisan a,lisan b)
{
  return a.data<b.data;
}
lisan l[301];
int n,t,s,e,edges[301][3],len,map[1001];
node now,c,res;
node mul(node a,node b)
{
  for (int i=1;i<=200;++i)
    for (int j=1;j<=200;++j)
      c.map[i][j]=1e9;
  for (int i=1;i<=200;++i)
    for (int j=1;j<=200;++j)
      for (int k=1;k<=200;++k)
	c.map[i][j]=min(c.map[i][j],a.map[i][k]+b.map[k][j]);
  return c;
}
node fast_pow(node a,int b)
{
  if (b==1)
    return a;
  if (b&1)
    return mul(fast_pow(mul(a,a),b/2),a);
  else
    return fast_pow(mul(a,a),b/2);
}
int main()
{
  int useless=0;
  cin>>n>>t>>s>>e;
  for (int i=1;i<=200;++i)
    for (int j=1;j<=200;++j)
      now.map[i][j]=(1e9);
  for (int i=1;i<=t;++i)
    {
      cin>>edges[i][2]>>edges[i][0]>>edges[i][1];
      l[++len].data=edges[i][0];
      l[len].num=len;
      l[++len].data=edges[i][1];
      l[len].num=len;
    }
  sort(l+1,l+len+1,cmp);
  for (int i=1;i<=len;++i)
    {
      l[i].newdata=i-useless;
      map[l[i].data]=l[i].newdata;
      if (l[i].data==l[i+1].data)
	  useless++;
    }
  sort(l+1,l+len+1);
  for (int i=1;i<=t;++i)
      now.map[l[i*2-1].newdata][l[i*2].newdata]=now.map[l[i*2].newdata][l[i*2-1].newdata]=min(now.map[l[i*2-1].newdata][l[i*2].newdata],edges[i][2]);
  res=fast_pow(now,n);
  cout<<res.map[map[s]][map[e]]<<endl;
  return 0;
}

标签:Cow,USACO07NOV,edges,min,矩阵,len,floyd,条边,Relays
From: https://www.cnblogs.com/zhouhuanyi/p/16983568.html

相关文章

  • 题解 洛谷 P2885 [USACO07NOV]Telephone Wire G
    1.题面描述题目链接给出\(n\)棵树的高度。你可以进行任意次操作,每次操作形如:把某棵树增高\(x\),代价为\(x^2\)(注意:不能将一棵树的高度减少)。在操作完之后,一个状态......
  • LeetCode: 299. Bulls and Cows
    LeetCode:299.BullsandCows题目描述YouareplayingthefollowingBullsandCowsgamewithyourfriend:Youwritedownanumberandaskyourfriendtoguessw......
  • 洛谷-P5541 Sleepy Cow Herding S
    SleepyCowHerdingSSleepyCowSorting的升级版,从\(3\)头牛变成\(n\)的情况分类讨论+双指针先把答案本就连续的特判丢掉最大值最大值就尽量把每个空位......
  • USACO 2019 January Contest, Bronze Problem 2. Sleepy Cow Sorting
    SleepyCowSorting分类讨论先把答案本就连续的特判丢掉最大值最大值就尽量把每个空位都踩一遍,模拟一下会发现,第一跳的空隙一定没办法踩到,因此考虑两边第一跳谁......
  • POJ-3263 Tallest Cow
    思路分析(摘自这篇博客)这道题目一个核心要点,就是如何处理这些特殊的关系,也就是两头牛互相看见。其实题目中已经告诉我们如何处理,因为我们发现,题目中要求牛的身高最高,那......
  • [边数限制最短路 倍增floyd 矩阵优化]Cow Relays G
    [边数限制最短路倍增floyd矩阵优化]CowRelaysG题目思路边数限制的最短路?bellman_ford可以拿来解决边数<=k的最短路,但这题是边数恰好为k,可以通过奇妙操作改成恰好经过k......
  • PICOW避坑-I2C
    1.I2C扫描出的地址“错误”看代码中I2C地址是0x78H,结果扫描出来是0x3c——没有注意到它们是两倍关系。I2C.scan()扫描出来的确实是地址,只有7bit,比如0x3c:0111100XB;写......
  • SP11469 SUBSET - Balanced Cow Subsets Sol
    考虑枚举\(3^n\)种情况,用三进制数表示。对于每一位,\(0\)表示不放,\(1\)表示放入第一个集合,\(2\)表示放入第二个集合。这样显然会TLE。考虑meetinthemiddle。考......
  • Til the Cows Come Home
    题目:题解:最短路模板#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#include<queue>#include<stack>#include<......
  • 【题解】洛谷P2946 [USACO09MAR]Cow Frisbee Team S
    这题乍一看是一个朴素的01背包问题,将所有方案的集合按照能力值的和来划分成1~m,然后把m当作体积,把n当作物品数,做一个01背包的代码。于是我兴冲冲地写了代码交上去,然后十组样......