首页 > 代码库 > [COCI2012Final]Pro1
[COCI2012Final]Pro1
校内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]$就是答案。
1 //OJ 1832 2 //by Cydiater 3 //2016.10.10 4 #include <iostream> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <queue> 9 #include <map>10 #include <ctime>11 #include <cmath>12 #include <string>13 #include <algorithm>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 const int MAXN=1e3+5;20 const int oo=0x3f3f3f3f;21 inline int read(){22 char ch=getchar();int x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 int N,M,e[MAXN][MAXN],cir[MAXN][MAXN],vis[MAXN][MAXN],a,b,min_cir;28 namespace solution{29 void init(){30 N=read();M=read();31 memset(e,10,sizeof(e));32 up(i,1,M){33 int x=read(),y=read();34 e[x][y]=1;35 }36 up(i,1,N)e[i][i]=0;37 }38 void slove(){39 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]);40 memset(cir,10,sizeof(cir));41 memset(vis,0,sizeof(vis));42 cir[2][2]=1;43 //up(i,1,N)vis[i][i]=1;44 while(1){45 a=-1;b=-1;min_cir=oo;46 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];47 if(a==1&&b==1)break;48 vis[a][b]=1;49 up(i,1,N)up(j,1,N)if(a!=i&&a!=j&&b!=i&&b!=j)50 cir[i][j]=min(cir[i][j],cir[a][b]+e[b][i]+e[i][j]+e[j][a]-1);51 }52 cout<<cir[1][1]<<endl;53 }54 }55 int main(){56 //freopen("input.in","r",stdin);57 using namespace solution;58 init();59 slove();60 return 0;61 }
[COCI2012Final]Pro1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。