Solução por Lucca Siaudzionis
Este problema consiste de dois sub-problemas:
- O primeiro consiste em calcular o custo de cada aresta do grafo. É um problema clássico de programação dinâmica (clique aqui para conferir nossa aula sobre o assunto).
- O segundo consiste em, tendo o custo de cada aresta, achar a Árvore Geradora Mínima (clique aqui para conferir nossa aula sobre o assunto).
O código, então, fica:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <cstring> | |
| #include <algorithm> | |
| using namespace std; | |
| struct t_edge{ | |
| int x; | |
| int y; | |
| int c; | |
| bool operator <(const t_edge q) const{ | |
| return c < q.c; | |
| } | |
| bool operator >(const t_edge q) const{ | |
| return c > q.c; | |
| } | |
| }; | |
| //------------------- | |
| #define MAXP 30 | |
| #define MAXT 105 | |
| #define MAXN 300 | |
| int n, p, e; | |
| int stone[MAXP]; | |
| int ways[MAXT][MAXP]; // número de maneiras de preencher cada aresta | |
| t_edge edge[MAXN*MAXN]; | |
| int pai[MAXN]; | |
| int rank[MAXN]; | |
| //------------------- | |
| int calc_way(int x, int ind){ | |
| register int i; | |
| if(x < 0) return 0; | |
| if(x == 0) return 1; | |
| if(ways[x][ind] != -1) return ways[x][ind]; | |
| ways[x][ind] = 0; | |
| for(i = ind;i <= p;i++) ways[x][ind] += calc_way(x - stone[i], i); | |
| return ways[x][ind]; | |
| } | |
| int find(int x){ | |
| if(pai[x] == x) return x; | |
| return pai[x] = find(pai[x]); | |
| } | |
| void join(int x, int y){ | |
| int xr = find(x); | |
| int yr = find(y); | |
| if(rank[xr] > rank[yr]) pai[yr] = xr; | |
| else if(rank[xr] < rank[yr]) pai[xr] = yr; | |
| else{ | |
| pai[yr] = xr; | |
| rank[xr]++; | |
| } | |
| } | |
| int main(){ | |
| register int i; | |
| memset(ways, -1, sizeof ways); | |
| scanf("%d %d %d", &n, &p, &e); | |
| for(i = 1;i <= p;i++) scanf("%d", &stone[i]); | |
| for(i = 1;i <= 100;i++) calc_way(i, 1); | |
| for(i = 1;i <= e;i++){ | |
| int c; | |
| scanf("%d %d %d", &edge[i].x, &edge[i].y, &c); | |
| edge[i].c = ways[c][1]; | |
| } | |
| sort(edge+1, edge+e+1); | |
| for(i = 1;i <= n;i++) pai[i] = i, rank[i] = 0; | |
| int total_cost = 0; | |
| for(i = 1;i <= e;i++) | |
| if(edge[i].c && (find(edge[i].x) != find(edge[i].y)) ) | |
| total_cost += edge[i].c, join(edge[i].x, edge[i].y); | |
| bool shit = false; | |
| find(1); | |
| for(i = 2;i <= n;i++) if(find(i) != pai[1]) shit = true; | |
| if(shit) printf("-1\n"); | |
| else printf("%d\n", total_cost); | |
| return 0; | |
| } |