次小生成树。求出两点间最短路径的最大权值,再把要加入的边与之比较即可。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int MAXN=;
const int MAXM=;
const int inf=;
int map[MAXN][MAXN];
int edge[MAXM][];
bool exist[MAXN][MAXN],used[MAXN][MAXN],vis[MAXN];
int f[MAXN][MAXN],dist[MAXN],pre[MAXN];
int m,n,q;
int ans1=;
void init(){
for(int i=;i<=n;i++){
vis[i]=false;
for(int j=i;j<=n;j++){
map[i][j]=map[j][i]=inf;
exist[i][j]=exist[j][i]=used[i][j]=used[j][i]=false;
f[i][j]=f[j][i]=;
}
}
} void prim(){
dist[]=;
for(int i=;i<=n;i++){
dist[i]=map[][i];
if(dist[i]!=inf)
pre[i]=;
else pre[i]=-;
}
vis[]=true;
for(int i=;i<=n;i++){
int min=inf,p=-;
for(int k=;k<=n;k++){
if(dist[k]<min&&!vis[k]){
min=dist[k]; p=k;
}
}
if(p==-) return ;
for(int k=;k<=n;k++){
if(vis[k]){
f[k][p]=max(f[k][pre[p]],map[pre[p]][p]);
f[p][k]=f[k][p];
}
}
vis[p]=true;
for(int k=;k<=n;k++){
if(!vis[k]&&map[p][k]<dist[k]){
dist[k]=map[p][k];
pre[k]=p;
}
}
}
} int main(){
int u,v,d;
int c,w;
while(scanf("%d%d%d",&n,&m,&q)!=EOF){
init();
for(int i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
edge[i][]=u; edge[i][]=v; edge[i][]=d;
if(d<map[u][v])
map[u][v]=map[v][u]=d;
}
prim();
for(int i=;i<=q;i++){
scanf("%d%d",&c,&w);
u=edge[c][]; v=edge[c][];
if(w<=f[u][v])
printf("Yes\n");
else printf("No\n");
}
}
return ;
}

最新文章

  1. Write thread-safe servlets [reproduced]
  2. 每天一个linux命令(57):ss命令
  3. Java设计模式(三) 装饰模式
  4. OptionParser
  5. 【C语言】函数和自定义函数
  6. Linux中的网络
  7. UVa 572 Oil Deposits(DFS)
  8. WebDriver(Selenium2) 根据新窗口title切换窗口
  9. 0基础搭建Hadoop大数据处理-环境
  10. gitlab 添加SSH Key
  11. WebService入门实例教程
  12. loadrunner录制脚本(一) ----录制脚本打不开浏览器
  13. java实现发送邮件服务器,SMTP协议发送邮件
  14. [HNOI 2013]比赛
  15. bestcoder round 74 div2
  16. Rabin-Karp ACM训练
  17. easyui datagrid 禁止选中行
  18. Web应用获取文件路径的方法
  19. openresty + lua 3、openresty http 调用
  20. Beta阶段冲刺-6

热门文章

  1. vue.js的第一个程序
  2. [Apple开发者帐户帮助]五、管理标识符(1)注册应用程序ID
  3. 【原创分析帖】据说Google内部有史以来最难的一道面试题
  4. Java调用JavaWebService
  5. 总结:Ruby里是值传递还是引用传递
  6. 《计算机图形学基础(OpenGL版)》勘误表
  7. .NET Core &amp; EntityFrameworkCore
  8. cmd 运行 svn 亲测!!!
  9. msmq消息队列使用场景
  10. C++泛型 &amp;&amp; Java泛型实现机制