HDU 4738--Caocao's Bridges【無向図辺双連通&&重み値最小のブリッジ&&テンプレート】
6862 ワード
Caocao's Bridges
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2641 Accepted Submission(s): 855
Problem 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 <= N
2 )
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
Sample Output
标题:n座島とm条橋があって、それぞれの橋の上でw人の兵士が守っていて、今橋を守る兵士の数より少なくない人を派遣して橋を爆破して、1本の橋を爆破することしかできなくて、このn座島がつながっていないようにして、少なくとも何人を派遣することを求めます.
解析:Tarjanアルゴリズムを用いて図中の重み値が最も小さいブリッジを求めるだけでよい.
注意:
一:図がつながっていない場合は、橋を爆破する必要はありません.直接0を出力します.
二:重いエッジがあるかもしれません
三:橋に兵士がいなければ、少なくとも一人を橋を爆破させなければならない.
もう一つのエッジを直す方法は、この問題にとって処理時間が遅い.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2641 Accepted Submission(s): 855
Problem 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 <= N
2 )
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
标题:n座島とm条橋があって、それぞれの橋の上でw人の兵士が守っていて、今橋を守る兵士の数より少なくない人を派遣して橋を爆破して、1本の橋を爆破することしかできなくて、このn座島がつながっていないようにして、少なくとも何人を派遣することを求めます.
解析:Tarjanアルゴリズムを用いて図中の重み値が最も小さいブリッジを求めるだけでよい.
注意:
一:図がつながっていない場合は、橋を爆破する必要はありません.直接0を出力します.
二:重いエッジがあるかもしれません
三:橋に兵士がいなければ、少なくとも一人を橋を爆破させなければならない.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 1010
#define maxm 1000100
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
int low[maxn];
int dfn[maxn];
int head[maxn], cnt;
int dfs_clock;
int mark;//
struct node{
int u, v, w, cnt, next;
};
node edge[maxm];
void init(){
cnt = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int w){
edge[cnt] = {u, v, w, 0, head[u]};
head[u] = cnt++;
edge[cnt] = {v, u, w, 0, head[v]};
head[v] = cnt++;
}
void input(){
while(m--){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
}
void tarjin(int u, int fa){
low[u] = dfn[u] = ++dfs_clock;
int flag = 1;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].v;
if(flag && v == fa){// ，
flag = 0;
continue;
}
if(!dfn[v]){
tarjin(v, u);
low[u] = min(low[u], low[v]);
if(dfn[u] < low[v])//
edge[i].cnt = edge[i ^ 1].cnt = 1;
}
else
low[u] = min(low[u], dfn[v]);
}
}
void find(){
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
dfs_clock = 0;
tarjin(1, 1);
mark = 1;
for(int i = 1; i <= n; ++i){
if(!dfn[i]){
mark = 0;
return ;
}
}
}
void solve(){
if(!mark)
printf("0
");
else{
int ans = INF;
for(int i = 0; i < cnt; ++i){
if(edge[i].cnt)
ans = min(ans, edge[i].w);
}
if(ans == INF)
ans = -1;
if(ans == 0)
ans = 1;
printf("%d
", ans);
}
}
int main (){
while(scanf("%d%d", &n, &m), n || m){
init();
input();
find();
solve();
}
return 0;
}
もう一つのエッジを直す方法は、この問題にとって処理時間が遅い.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 1010
#define maxm 1000100
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
int low[maxn];
int dfn[maxn];
int head[maxn], cnt;
int dfs_clock;
int mark;//
struct node{
int u, v, w, cnt, next, again;//again
};
node edge[maxm];
void init(){
cnt = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int w){
int i;
//
for(i = head[u]; i != -1; i = edge[i].next){
if(edge[i].v == v){
break;
}
}
if(i != -1)
edge[i].again = 1;
else{
edge[cnt] = {u, v, w, 0, head[u], 0};
head[u] = cnt++;
}
}
void input(){
while(m--){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
}
void tarjin(int u, int fa){
low[u] = dfn[u] = ++dfs_clock;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].v;
if(v == fa) continue;
if(!dfn[v]){
tarjin(v, u);
low[u] = min(low[u], low[v]);
if(dfn[u] < low[v] && edge[i].again == 0)//
edge[i].cnt = edge[i ^ 1].cnt = 1;
}
else
low[u] = min(low[u], dfn[v]);
}
}
void find(){
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
dfs_clock = 0;
tarjin(1, -1);
mark = 1;
for(int i = 1; i <= n; ++i){
if(!dfn[i]){
mark = 0;
return ;
}
}
}
void solve(){
if(!mark)
printf("0
");
else{
int ans = INF;
for(int i = 0; i < cnt; ++i){
if(edge[i].cnt)
ans = min(ans, edge[i].w);
}
if(ans == INF)
ans = -1;
if(ans == 0)
ans = 1;
printf("%d
", ans);
}
}
int main (){
while(scanf("%d%d", &n, &m), n || m){
init();
input();
find();
solve();
}
return 0;
}