Pagini recente » Cod sursa (job #3239694) | Cod sursa (job #2607314) | Cod sursa (job #270071) | Cod sursa (job #584494) | Cod sursa (job #2896988)
#include <fstream>
#include <vector>
using namespace std;
struct Edge {
int u;
int v;
int cost;
};
bool operator < (const Edge &a, const Edge &b) {
return a.cost < b.cost;
}
const int MAX_N = 2 * 1e8;
int parent[MAX_N + 1], t[MAX_N + 1];
vector<Edge> edges;
void init() {
for (int i = 1; i <= MAX_N; i++) {
parent[i] = i;
t[i] = 1;
}
}
int root(int u) {
if (parent[u] == u) {
return u;
}
return parent[u] = root(parent[u]);
}
bool areJoined(int u, int v) {
return root(u) == root(v);
}
void unite(int u, int v) {
u = root(u);
v = root(v);
if (u != v) {
if (t[u] < t[v]) {
swap(u, v);
}
parent[v] = parent[u];
t[v] += t[u];
}
}
int main() {
ifstream fin("adunare.in");
ofstream fout("adunare.out");
int a, b;
fin >> a >> b;
for (int i = 1; i <= a + b; i++) {
edges.push_back(Edge {i, i + 1, 1});
}
init();
int answer = 0;
for (Edge e : edges) {
if (areJoined(e.u, e.v) == false) {
unite(e.u, e.v);
answer += e.cost;
}
}
fout << answer;
return 0;
}