Untitled
unknown
c_cpp
19 days ago
2.0 kB
6
Indexable
Never
#include <bits/stdc++.h> using namespace std; const int MAX = 30; const long long INF = (1LL<<60); struct DSU { vector<int> p; int comps; // número de componentes conexas DSU(int n) { // define tamanho N e valor padrão 0 a "p" p.assign(n+1, 0); // define os pais padrão dos vertices iota(p.begin(), p.end(), 0); // conta de 0 até N e espalha os valores entre as devidas posições do array "p" comps = n; } int id(int u) { return (p[u] == u ? u : p[u] = id(p[u])); } void join(int u, int v) { p[u] = v; --comps; } }; struct S { int u, v; long long w; } ns[MAX]; int N, M; long long K; // solução ótima global long long ans = INF; // backtracking | escolhendo no pior caso 8 elementos num array de tamanho 28 void back(int i, int m) { // se tiver N - 1 marcações então temos um caso pronto if(__builtin_popcount(m) == N - 1) { // conta quantos 1's tem na bitmask // solução ótima local long long soma = 0; DSU dsu(N); // passamos por todas as arestas for(int i = 0; i < M; ++i) { // se a aresta "i" estiver marcada if((1<<i) & m) { const int U = dsu.id(ns[i].u), V = dsu.id(ns[i].v); // se a MST forma um ciclo if(U == V) return; dsu.join(U, V); soma = ((soma % K) + (ns[i].w % K)) % K; } } // minimizamos a solução ótima global ans = min(ans, soma); return; } // se já chegamos a ultima posição do array de arestas if(i == M) return; // testando solução sem considerar a aresta i back(i+1, m); // marcando a aresta i na bitmask m |= (1<<i); // testando solução considerando a aresta i back(i+1, m); } signed main() { cin.tie(nullptr)->sync_with_stdio(0); cin>>N>>M>>K; for(int i = 0; i < M; ++i) { cin>>ns[i].u>>ns[i].v>>ns[i].w; } back(0, 0); cout<<ans<<'\n'; }
Leave a Comment