HDU4738:Caocao's Bridges(求桥)
Caocao's Bridges
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8476 Accepted Submission(s): 2604
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4738
Description:
Caocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn't give up. Caocao's army still was not good at water battles, so he came up with another idea. He built many islands in the Changjiang river, and based on those islands, Caocao's army could easily attack Zhou Yu's troop. Caocao also built bridges connecting islands. If all islands were connected by bridges, Caocao's army could be deployed very conveniently among those islands. Zhou Yu couldn't stand with that, so he wanted to destroy some Caocao's bridges so one or more islands would be seperated from other islands. But Zhou Yu had only one bomb which was left by Zhuge Liang, so he could only destroy one bridge. Zhou Yu must send someone carrying the bomb to destroy the bridge. There might be guards on bridges. The soldier number of the bombing team couldn't be less than the guard number of a bridge, or the mission would fail. Please figure out as least how many soldiers Zhou Yu have to sent to complete the island seperating mission.
Input:
There are no more than 12 test cases.
In each test case:
The first line contains two integers, N and M, meaning that there are N islands and M bridges. All the islands are numbered from 1 to N. ( 2 <= N <= 1000, 0 < M <= N2 )
Next M lines describes M bridges. Each line contains three integers U,V and W, meaning that there is a bridge connecting island U and island V, and there are W guards on that bridge. ( U ≠ V and 0 <= W <= 10,000 )
The input ends with N = 0 and M = 0.
Output:
For each test case, print the minimum soldier number Zhou Yu had to send to complete the mission. If Zhou Yu couldn't succeed any way, print -1 instead.
Sample Input:
3 3
1 2 7
2 3 4
3 1 4
3 2
1 2 7
2 3 4
0 0
Sample Output:
-1
4
题意:
给出一个无向图,然后每条边都有边权,求所有桥的最小边权。若不存在桥,输出-1。
题解:
这个就直接dfs一下,利用时间戳来求桥就行了。但是注意如果边权为0的时候,答案为1。。因为至少需要一个人去搬炸弹。
代码如下:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int N = ;
int n,m,tot;
int head[N];
struct Edge{
int u,v,next,w;
}e[N*N<<];
int T;
int dfn[N],low[N],cut[N*N];
void adde(int u,int v,int w){
e[tot].u=u;e[tot].v=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot++;
}
void init(){
T=;tot=;
memset(head,-,sizeof(head));
memset(cut,,sizeof(cut));
memset(dfn,,sizeof(dfn));
}
void Tarjan(int u,int pre){
dfn[u]=low[u]=++T;
int k = ;
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
if(v==pre &&!k){
k=;
continue ;
}
if(!dfn[v]){
Tarjan(v,u);
low[u]=min(low[u],low[v]);
}else{
low[u]=min(low[u],dfn[v]);
}
if(low[v]>dfn[u]){
cut[i]=cut[i^]=;
}
}
}int main(){
while(scanf("%d%d",&n,&m)!=EOF){
if(n+m<=) break;
init();
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
adde(u,v,w);adde(v,u,w);
}
int cnt = ;
for(int i=;i<=n;i++){
if(!dfn[i]){
Tarjan(i,i);
cnt++;
}
}
if(cnt>){
cout<<<<endl;
continue ;
}
int ans = 0x3f3f3f3f;
for(int i=;i<tot;i+=){
if(cut[i])ans=min(ans,e[i].w);
}
if(ans==0x3f3f3f3f) puts("-1");
else cout<<max(ans,)<<endl;
}
return ;
}
最新文章
- 使用spring过程中遇到的问题
- hdu1005 矩阵
- java 、android 知识图谱
- JavaScript Web Application summary
- Hadoop高可用平台搭建
- 2015华为德州扑克入境摘要——软体project
- 在Action类中获得HttpServletResponse对象的四种方法
- 高吞吐koa日志中间件
- pt工具主从一致性检查并修复以及版本3.0.4的版本缺点
- restful状态码常用
- 通过xml处理sql语句时对小于号与大于号的处理转换
- (转)SQLServer查询数据库各种历史记录
- dotnet core 编程规范
- python 全栈开发,Day124(MongoDB初识,增删改查操作,数据类型,$关键字以及$修改器,";$";的奇妙用法,Array Object 的特殊操作,选取跳过排序,客户端操作)
- ansible进阶模板和角色使用
- Lua协程学习
- sublime text注册码与快捷键
- 删除节点removeChild()
- 用 Sqlmap 识别 WAF
- Spket,eclipse下安装Spket插件,格式化js