【HDU4034】Graph
2024-10-07 04:29:40
题目大意:给定一个图的最短路,求原图中至少存在多少条边。
题解:利用 Floyd 的性质,枚举边 d[i][j],若存在一个不是两端点的点,使得 d[i][j]=d[i][k]+d[k][j] 成立,则证明 (i,j) 这条边可以没有。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
int n,d[maxn][maxn];
int kase;
void read_and_parse(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&d[i][j]);
}
void solve(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(d[i][j]>d[i][k]+d[k][j])
return (void)printf("Case %d: impossible\n",++kase);
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j)continue;
bool is=1;
for(int k=1;k<=n;k++){
if(k!=i&&k!=j&&d[i][j]==d[i][k]+d[k][j]){
is=0;
break;
}
}
if(is)++ans;
}
printf("Case %d: %d\n",++kase,ans);
}
int main(){
int T;scanf("%d",&T);
while(T--){
read_and_parse();
solve();
}
return 0;
}
最新文章
- matlab 求解线性方程组之范数
- ecshop二次开发常用代码
- 一种感觉不太好的设置radioButton的方法
- 5.servlet cookie自动登录的实例
- LCA算法
- 最清晰的ios消息推送机制教程
- 一个坑:java.sql.ResultSet.getInt==》the column value; if the value is SQL NULL, the value returned is 0
- SendMessage的返回值,就是由相应的响应消息函数的返回值(解释的简洁明了)
- oracle_PLSQL 快捷键使用技巧
- 201521123121 《JAVA程序设计》第8周学习总结
- 理解Python中的装饰器//这篇文章将python的装饰器来龙去脉说的很清楚,故转过来存档
- 41.找出所有和为S的连续正数序列
- AMS工作原理—— App启动概要
- day42 事物,数据库锁
- jvm内存模型中-栈,方法区,程序计数器是线程安全的
- sha0dow0socks
- 在free bsd上跑JMeter 的 plugin ";PerfMon Server Agent";
- Codeforces 912E - Prime Gift
- centos下安装升级python到python3.5
- mysql安装 卸载 查字符集编码