題目鏈接：點擊查看

題目大意：給出n和m然后給出n條橫向街道和m條縱向街道，總共包括了n*m個結點，每條街道都是單向通道，問該圖是否能夠組成強聯通圖（有向圖中任意兩點間都存在路徑）

題目分析：乍一看沒感覺和最短路有關系，其實可以轉換為Floyd的思想，Floyd是可以以n*n*n的時間復雜度求出每兩個點之間的最短路，我們只需要將賦值改變一下就可以判斷每兩個點之間的聯通性了，因為給出的是一個矩陣，n和m最大只有20，所以至多有400個點，這個數據范圍正好可以用Floyd跑一遍，一開始先根據題目要求建好圖，直接跑一遍再判斷一遍就出結果了，挺簡單的一個題，主要是思路得想到

---

2019年11月17日更新：

原來這是個思維題emmmm

只用判斷一下四周的四條邊能否順時針或逆時針組成一個圈就行了，為什么呢？因為通過每一個點肯定能順著到達周圍的四條邊，通過周圍的四條邊就能遍歷所有的每一行每一列了

這里我用了一個四維數組maze[x][y][xx][yy]來記錄點（x，y）到點（xx，yy）的聯通性，直接上代碼了：

Floyd：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=25;int n,m;int maze[N][N][N][N];bool check()//判斷聯通性，若兩個點之間的最短路為0則聯通，為inf則為不聯通 {for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int ii=1;ii<=n;ii++)for(int jj=1;jj<=m;jj++)if(maze[i][j][ii][jj]==inf)return false;return true; }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)//初始化for(int j=1;j<=m;j++)for(int ii=1;ii<=n;ii++)for(int jj=1;jj<=m;jj++)maze[i][j][ii][jj]=(i==ii&&j==jj)?0:inf; string x,y;cin>>x>>y;x=" "+x;y=" "+y;for(int i=1;i<=n;i++)//根據題目要求建邊{if(x[i]=='>'){for(int j=1;j<m;j++)maze[i][j][i][j+1]=0;}else if(x[i]=='<'){for(int j=m;j>1;j--)maze[i][j][i][j-1]=0;}}for(int j=1;j<=m;j++){if(y[j]=='v'){for(int i=1;i<n;i++)maze[i][j][i+1][j]=0;}else if(y[j]=='^'){for(int i=n;i>1;i--)maze[i][j][i-1][j]=0;}}for(int k=1;k<=n;k++)//Floydfor(int kk=1;kk<=m;kk++)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int ii=1;ii<=n;ii++)for(int jj=1;jj<=m;jj++)if(maze[i][j][k][kk]+maze[k][kk][ii][jj]<maze[i][j][ii][jj])maze[i][j][ii][jj]=maze[i][j][k][kk]+maze[k][kk][ii][jj];if(check())printf("YES\n");elseprintf("NO\n");}return 0; }

思維：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;char a[N],b[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);scanf("%s%s",a+1,b+1);if(a[1]=='<'&&a[n]=='>'&&b[1]=='v'&&b[m]=='^')puts("YES");else if(a[1]=='>'&&a[n]=='<'&&b[1]=='^'&&b[m]=='v')puts("YES");elseputs("NO");return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 475B Strongly Connected City(最短路+判断强联通图/思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。