STDIN/STDOUT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<utility> #include<algorithm> #include<map> #include<vector> #include<list> #include<functional> #include<string> using namespace std; int u[10005], v[10005], w[10005], first[105], nxt[10005]; int n, m; bool control[105],visited[105]; int percentage[105]; void dfs(int node) { if (visited[node])return; visited[node] = true; for (int e = first[node]; e != -1; e = nxt[e]) { percentage[v[e]] += w[e]; if (percentage[v[e]] > 50) { control[v[e]] = true; dfs(v[e]); } } } int main() { memset(first, -1, sizeof(first)); cin >> n; for (int i = 1; i <= n; i++) { cin >> u[i] >> v[i] >> w[i]; nxt[i] = first[u[i]]; first[u[i]] = i; m = max(m, max(u[i], v[i])); } for (int i = 1; i <= m; i++) { memset(visited, false, sizeof(visited)); memset(control, false, sizeof(control)); memset(percentage, 0, sizeof(percentage)); dfs(i); for (int j = 1; j <= m; j++) { if (i != j&&control[j])cout << i << " " << j << endl; } } } |