[COCI2012Final]Pro1
2024-08-21 02:13:24
校内OJ上的题。
数据范围非常小,用暴搜就可以,加点剪枝阶乘级别的复杂度竟然可以跑得比$O(N^4)$的算法还要快QAQ。
我用的是Floyd,参考了别人的代码。大概就是先跑个Floyd把点点之间路径处理出来,也就是从一个点到另一个点最少要经过多少点。然后设$cir[a][b]$表示,$node_a$和$node_b$在一个经过标号为2的点的环里,最少需要经过的点。
剩下的过程比较像dijkstra的流程,先把$cir[2][2]$的初值定为1。然后每次取出最小的,未被取出过的$cir[a][b]$,对于任意点$node_i$和$node_j$,可以得到$cir[i][j]=cir[a][b]+e[b][i]+e[i][j]+e[j][a]-1$,这个方程画个图就差不多能看懂。
最后$cir[1][1]$就是答案。
//OJ 1832 //by Cydiater //2016.10.10 #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <map> #include <ctime> #include <cmath> #include <string> #include <algorithm> #include <iomanip> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) const int MAXN=1e3+5; const int oo=0x3f3f3f3f; inline int read(){ char ch=getchar();int x=0,f=1; while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int N,M,e[MAXN][MAXN],cir[MAXN][MAXN],vis[MAXN][MAXN],a,b,min_cir; namespace solution{ void init(){ N=read();M=read(); memset(e,10,sizeof(e)); up(i,1,M){ int x=read(),y=read(); e[x][y]=1; } up(i,1,N)e[i][i]=0; } void slove(){ up(k,1,N)up(j,1,N)up(i,1,N)e[i][j]=min(e[i][j],e[i][k]+e[k][j]); memset(cir,10,sizeof(cir)); memset(vis,0,sizeof(vis)); cir[2][2]=1; //up(i,1,N)vis[i][i]=1; while(1){ a=-1;b=-1;min_cir=oo; up(i,1,N)up(j,1,N)if((cir[i][j]<min_cir&&!vis[i][j]))a=i,b=j,min_cir=cir[i][j]; if(a==1&&b==1)break; vis[a][b]=1; up(i,1,N)up(j,1,N)if(a!=i&&a!=j&&b!=i&&b!=j) cir[i][j]=min(cir[i][j],cir[a][b]+e[b][i]+e[i][j]+e[j][a]-1); } cout<<cir[1][1]<<endl; } } int main(){ //freopen("input.in","r",stdin); using namespace solution; init(); slove(); return 0; }
最新文章
- Dev 13.2 汉化教程(提供汉化cs文件下载)
- maven认证信息
- Sharepoint学习笔记—习题系列--70-576习题解析 -(Q13-Q15)
- .NET程序迁移到Mysql的极简方案——让GGTalk同时支持Sqlserver与mysql全程记录!
- paper 84:机器学习算法--随机森林
- IOS开发之——使用Segue在StoryBoard之间切换
- poj 2288 tsp经典问题
- OpenGL屏幕二维坐标转化成三维模型坐标
- css div旋转之后自适应
- 九度OJ 1006 ZOJ
- VS Code 编辑器
- Java面向对象的三大特性之一 多态
- java http大文件断点续传上传
- CentOS 7 系统root用户忘记密码的重置方法
- 【Android】详解Android的menu菜单
- Running Protractor Tests on Docker
- phpexcel表的一些设置
- Appcompat实现Action Bar的兼容性处理
- 菜鸟学习Spring——SpringMVC注解版解析不同格式的JSON串
- 按F12 IE浏览器的开发工具打不开解决方法