Um_nik

Untitled

Sep 14th, 2014
456
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. typedef long long lld;
  7.  
  8. int T = 0;
  9.  
  10. struct Vertex {
  11. vector< int > neighs;
  12. lld limit;
  13. double cur;
  14. int T_out, index;
  15. };
  16.  
  17. inline bool operator <(const Vertex &a, const Vertex &b) {
  18. return a.T_out > b.T_out;
  19. }
  20.  
  21. Vertex *nodes;
  22.  
  23. void DFS(int vertex) {
  24. for (unsigned i = 0; i < nodes[vertex].neighs.size(); i++)
  25. DFS(nodes[vertex].neighs[i]);
  26. nodes[vertex].T_out = ++T;
  27. }
  28.  
  29. int main() {
  30. freopen("input.txt", "r", stdin); //
  31.  
  32. int N, K;
  33. scanf("%d%d", &N, &K);
  34. nodes = new Vertex [N];
  35. for (int i = 0; i < N; i++) {
  36. scanf("%lld%lf", &nodes[i].limit, &nodes[i].cur);
  37. nodes[i].index = i;
  38. }
  39. for (int i = 0; i < K; i++) {
  40. int F, T;
  41. scanf("%d%d", &F, &T);
  42. F--;
  43. T--;
  44. nodes[F].neighs.push_back(T);
  45. }
  46. int start, target;
  47. lld start_adding;
  48. scanf("%d%lld%d", &start, &start_adding, &target);
  49. start--;
  50. target--;
  51.  
  52. DFS(start);
  53. sort(nodes, nodes + N);
  54.  
  55. nodes[0].cur += start_adding;
  56. int i;
  57. for (i = 0; i < N; i++) {
  58. printf("%d:\n", nodes[i].index); //
  59. if (nodes[i].cur > nodes[i].limit) {
  60. double adding = (nodes[i].cur - nodes[i].limit) / nodes[i].neighs.size();
  61. printf(" adding = %.2lf\n", adding); //
  62. for (unsigned j = 0; j < nodes[i].neighs.size(); i++)
  63. nodes[nodes[i].neighs[j]].cur += adding;
  64. }
  65. }
  66. printf("%.4lf\n", min(nodes[i].cur, static_cast< double > (nodes[i].limit)));
  67. return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment