Created
June 22, 2015 01:51
-
-
Save luccasiau/7e7fbca8b3cb749fd640 to your computer and use it in GitHub Desktop.
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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment