Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1809
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1809
Secret Agents
By Unknown 
Brazil
Timelimit: 0
All people who have seen the movies or series of espionage like 007, Mission Impossible or Hawaii 5-0, know that some countries of the world keeps groups of undercover intelligence agents in governments and organizations in the Middle East , South America and Eastern Europe .
An intelligence service has n agents scattered in a not very friendly country. Each agent knows other agents and has specific procedures to arrange a secret meeting with each one of them. Coded messages are usually exchanged to arrange such meetings. Given two agents i and j who known each other, there is a certain probability pij of a message exchanged between them is intercepted by hostile individuals.
From time to time, the leader of the intelligence service needs to disseminate confidential information to all his field agents. To do so, he uses the messaging mechanism of the agents, ie, he contacts some of these agents he knows and they are responsible for propagating the information so that the probability of interception P is minimal. As you can see, the service is so secret that not even the leader knows all his subordinate agents. Your task in this problem is to build a program that calculates P.
Input
Your program should be prepared to work on different scenarios, ie, several broadcasts confidential information in various countries. Each scenario is described in the following way. The first line specifies the number of agents in the country, 0 < n ≤ 100, including the leader of the intelligence service, and the number of pairs of agents who are in the country and known each other, 0 ≤ m ≤ 4950. Each of the following m lines contains two integers i, j and a rational pij, 1 ≤ i, j ≤ n and 0 ≤ pij ≤ 1. Each line means that agents i and j know each other and that a message exchanged between them is intercepted with probability pij. A zero value for n indicates the end of the scenarios. You can assume that it will always be possible to transmit confidential information between all agents.
Output
For each scenario the input, your program should print the text Cenario x, probabilidade de interceptacao = P, where x is the position of the respective scenario in the input file (numbered from 1) and P the probability of the information being disseminated to be intercepted. This probability should be printed with three decimal places. You must leave a blank line between each scenario.
| Sample Input | Sample Output |
|
4 6 1 2 0.3 1 3 0.1 1 4 0.5 2 3 0.9 2 4 0.1 3 4 0.5 3 2 1 2 1.0 2 3 1.0 0 0 |
Cenario 1, probabilidade de interceptacao = 0.433 Cenario 2, probabilidade de interceptacao = 1.000 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <vector>
#define MAXN 101
#define MP make_pair
using namespace std;
typedef pair < int, int> ii;
typedef pair dii;
int pai[MAXN], n, m, cenario;
vector < dii> Kruskal;
int find(int x) {
if (x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
if (x > y) swap(x, y);
pai[y] = x;
}
int main() {
while (scanf("%d %d", &n, &m) && (n || m)) {
if (cenario++) printf("\n");
Kruskal.clear();
for (int i = 1; i < = n; i++) {
pai[i] = i;
}
for (int i = 1; i < = m; i++) {
int u, v;
double peso;
scanf("%d %d %lf", &u, &v, &peso);
Kruskal.push_back(MP(1.0 - peso, MP(u, v)));
}
sort(Kruskal.begin(), Kruskal.end());
double prob = 1.0;
for (int i = m - 1; i >= 0; i--) {
if (find(Kruskal[i].second.first) !=
find(Kruskal[i].second.second)) {
join(Kruskal[i].second.first, Kruskal[i].second.second);
prob *= Kruskal[i].first;
}
}
printf("Cenario %d, probabilidade de interceptacao = %.3lf\n", cenario,
1.0 - prob);
}
return 0;
}
Input
1 2 0.3
1 3 0.1 1 4 0.5
2 3 0.9
2 4 0.1
3 4 0.5
3 2
1 2 1.0
2 3 1.0
0 0
Output
Cenario 2, probabilidade de interceptacao = 1.000