解题思路: 将地道的站点化作无向图,然后依次假设各个站点被炸毁,如果被炸毁后无法到达目标站点则被炸毁的站点就是关键站点,那么危险系数就+1.
注意事项:
参考代码:
#include<bits/stdc++.h> using namespace std; int n,m; int ma[1005][1005]; int u,v; int f[1005];//表示该站点是否已经走过 int ff[1005];//表示该站点是否炸毁 int flag=0; void dfs(int u,int v) { f[u]=1;//表示该站点走过了 if(u==v)//到达终点站点 { flag=1;//标记到达了终点 return; } for(int i=1;i<=n;i++) { if(ma[u][i]==1&&f[i]!=1&&ff[i]==0) { dfs(i,v); } } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++)//建立无向图 { int a,b; scanf("%d%d",&a,&b); ma[a][b]=1; ma[b][a]=1; } int ans=0;//危险系数 scanf("%d%d",&u,&v); dfs(u,v);//先试验所给的两个站点是否相通 if(flag==0)//不通就输出-1 { printf("-1"); return 0; } flag=0; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { if(i==u||i==v)//不能假设起点站和终点站被炸毁 { continue; } ff[i]=1;//当前站点被炸毁 dfs(u,v); ff[i]=0;//恢复当前站点 if(flag==0)//无法联通说明是关键站点 { ans++; } flag=0; memset(f,0,sizeof(f)); } printf("%d",ans); return 0; }
0.0分
0 人评分
【数组的距离】 (C语言代码)浏览:728 |
printf基础练习2 (C语言代码)浏览:942 |
校门外的树 (C语言代码)浏览:957 |
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1356 |
三角形 (C++代码)递归(存在大量重复计算,容易出现时间超限)浏览:779 |
1011题解浏览:762 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:562 |
1124题解浏览:594 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:487 |
输入输出格式练习 (C语言代码)浏览:746 |