首页 > 代码库 > 【动态规划】【最短路】【spfa】bzoj1207 [HNOI2004]打鼹鼠
【动态规划】【最短路】【spfa】bzoj1207 [HNOI2004]打鼹鼠
<法一>若打了一只鼹鼠后，还能打另一只，我们可以在它们之间连权值为1的边。于是答案就是 以m为终点的最长路长度+1。建反图，就是单源最长路。
MLE TLE 一时爽。
1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 vector<int>G[10001]; 7 queue<int>q; 8 int n,m,T[10001],x[10001],y[10001],dis[10001],ans; 9 bool inq[10001];10 void spfa(const int &s)11 {12 memset(dis,0xaf,sizeof(dis)); dis[s]=0;13 q.push(s); inq[s]=1;14 while(!q.empty())15 {16 int U=q.front();17 for(vector<int>::iterator it=G[U].begin();it!=G[U].end();it++)18 if(dis[*it]<dis[U]+1)19 {20 dis[*it]=dis[U]+1;21 if(!inq[*it])22 {23 q.push(*it);24 inq[*it]=1;25 }26 }27 q.pop(); inq[U]=0;28 }29 for(int i=1;i<=m;i++) ans=max(ans,dis[i]);30 }31 int Abs(const int &x){return x<0 ? -x : x;}32 int Dis(const int &x1,const int &y1,const int &x2,const int &y2)33 {return Abs(x1-x2)+Abs(y1-y2);}34 int main()35 {36 scanf("%d%d",&n,&m);37 for(int i=1;i<=m;i++) scanf("%d%d%d",&T[i],&x[i],&y[i]);38 for(int i=1;i<=m;i++)39 for(int j=i+1;j<=m;j++)40 if(T[j]-T[i]>=Dis(x[i],y[i],x[j],y[j]))41 G[j].push_back(i);42 spfa(m); printf("%d\n",ans+1);43 return 0;44 }
<法二>然后是m^2 暴力dp。100分。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int f[10001],T[10001],x[10001],y[10001]; 5 int Abs(const int &x){return x<0 ? -x : x;} 6 int Dis(const int &x1,const int &y1,const int &x2,const int &y2) 7 {return Abs(x1-x2)+Abs(y1-y2);} 8 int n,m; 9 int main()10 {11 scanf("%d%d",&n,&m);12 for(int i=1;i<=m;i++) scanf("%d%d%d",&T[i],&x[i],&y[i]);13 fill_n(f+1,m,1);14 for(int i=1;i<=m;i++)15 for(int j=1;j<i;j++)16 if(T[i]-T[j]>=Dis(x[i],y[i],x[j],y[j]))17 f[i]=max(f[i],f[j]+1);18 printf("%d\n",*max_element(f+1,f+m+1));19 return 0;20 }
【动态规划】【最短路】【spfa】bzoj1207 [HNOI2004]打鼹鼠
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。