Commits

danielmaxx committed d4b2cab

Soluciones de network modificadas y statues agregada.

--
danielmaxx

Comments (0)

Files changed (5)

solutions/network-danielmaxx.cpp

 	for(int ic=1; ic<=T; ++ic) {
 		scanf("%d %d", &N, &M);
 		graph gr(N*2 + M + 2);
+        int sink = gr.vertex-1;
+        int source = gr.vertex-2;
 		for(int i=0; i<N; ++i) {
 			int C; scanf("%d %d %d %d", &C, &range[i], &posTrans[i][0], &posTrans[i][1]);
 			gr.add_edge(i, N+i, C);
 			gr.add_edge(N+i, i, 0);
-			gr.add_edge(gr.vertex-2, i, INF);
-			gr.add_edge(i, gr.vertex-2, 0);
+			gr.add_edge(sink, i, 0);
+			gr.add_edge(i, sink, INF);
 		}
 		for(int i=0; i<M; ++i) {
 			scanf("%d %d", &posClients[i][0], &posClients[i][1]);
 			for(int j=0; j<N; ++j) {
 				const int tx = posTrans[j][0], ty = posTrans[j][1], r = range[j];
 				if( (tx-cx)*(tx-cx) + (ty-cy)*(ty-cy) <= r*r ) {
-					gr.add_edge(N+j, N*2 + i, 1);
-					gr.add_edge(N*2 + i, N+j, 0);
+					gr.add_edge(j, N*2 + i, 0);
+					gr.add_edge(N*2 + i, j, 1);
 				}
 			}
-			gr.add_edge(N*2 + i, gr.vertex - 1, INF);
-			gr.add_edge(gr.vertex - 1, N*2 + i, 0);
+			gr.add_edge(N*2 + i, source, 0);
+			gr.add_edge(source, N*2 + i, 1);
 		}
-		const int flow = gr.maxFlow(N*2 + M, N*2 + M + 1);
+		const int flow = gr.maxFlow(source, sink);
 		printf("Caso #%d: %d\n", ic, flow);
+        //gr.print(stdout);
 	}
 	return 0;
 }

solutions/network-zyx.cpp

 #include <deque>
 #include <limits>
 #include <stdio.h>
-#include <string.h>
 #include <stdlib.h>
+#include <string.h>
 using namespace std;
 
 // BEGIN CUT HERE
       for (int j = 0; j < N; ++j) if (d(x, y, X[j], Y[j]) <= R[j])
       {
         graph.AddEdge(base + i, j + 2, 1);
-        graph.AddEdge(source, base + i, 1);
       }
+      graph.AddEdge(source, base + i, 1);
     }
     int flow = graph.CreateFlow(source, sink);
-    printf("Caso #%d: %d\n", t, flow);
+    printf("Case #%d: %d\n", t, flow);
   }
   return 0;
 }

solutions/statues-zyx.cpp

+#include <stdio.h>
+#include <memory.h>
+#include <queue>
+#include <vector>
+#include <string>
+using namespace std;
+
+bool visited[11][11][11][11][11][11];
+
+int M, N, x;
+
+struct State
+{
+  int Kx, Ky, Lx, Ly, Px, Py;
+  State(int _Kx, int _Ky,int _Lx,int _Ly, int _Px, int _Py) :
+    Kx(_Kx),
+    Ky(_Ky),
+    Lx(_Lx),
+    Ly(_Ly),
+    Px(_Px),
+    Py(_Py)
+  {}
+};
+
+
+int main()
+{
+  int dx[] = { -1, 1, 0, 0 };
+  int dy[] = { 0, 0, -1, 1 };
+  int in[] = { 1, 0, 3, 2 };
+  freopen("statues.in", "rt", stdin);
+  //freopen("statues.out", "wt", stdout);
+  int T;
+  scanf("%d", &T);
+  for (int t = 1; t <= T; ++t)
+  {
+    int Kx, Ky, Lx, Ly, Px, Py, Ktx, Kty, Ltx, Lty;
+    scanf("%d%d%d%d%d%d%d%d%d%d%d%d%d", &Kx, &Ky, &Lx, &Ly, &Px, &Py, &Ktx, &Kty, &Ltx, &Lty, &M, &N, &x);
+    vector<string> board;
+    for (int i = 0; i < M; ++i)
+    {
+      char line [ 16 ];
+      scanf("%s", line);
+      board.push_back(line);
+    }
+    memset(visited, false, sizeof(visited));
+    queue<State> Q1, Q2;
+    queue<State> *q1 = &Q1, *q2 = &Q2;
+    Q2.push(State(Kx, Ky, Lx, Ly, Px, Py));
+    visited[Kx][Ky][Lx][Ly][Px][Py] = true;
+    int cost = 0;
+    int sol = Kx == Ktx && Ky == Kty && Lx == Ltx && Ly == Lty ? 0 : -1;
+    while (sol < 0 && ++cost <= x && !q2->empty())
+    {
+      swap(q1, q2);
+      while (sol < 0 && !q1->empty())
+      {
+        State const& state = q1->front();
+        for (int i = 0; i < 4; ++i)
+        {
+          int nKx = dx[in[i]] + state.Kx;
+          int nKy = dy[in[i]] + state.Ky;
+          int nLx = dx[i] + state.Lx;
+          int nLy = dy[i] + state.Ly;
+          int nPx = dx[i] + state.Px;
+          int nPy = dy[i] + state.Py;
+          if (nPx < 0 || nPx >= M || nPy < 0 || nPy >= N || board[nPx][nPy] == '*') continue;
+          if (nKx < 0 || nKx >= M || nKy < 0 || nKy >= N || board[nKx][nKy] == '*')
+          {
+            nKx = state.Kx;
+            nKy = state.Ky;
+          }
+          if (nLx < 0 || nLx >= M || nLy < 0 || nLy >= N || board[nLx][nLy] == '*')
+          {
+            nLx = state.Lx;
+            nLy = state.Ly;
+          }
+          if (nPx == nKx && nPy == nKy) continue;
+          if (nPx == nLx && nPy == nLy) continue;
+          if (nKx == nLx && nKy == nLy)
+          {
+            nKx = state.Kx;
+            nKy = state.Ky;
+            nLx = state.Lx;
+            nLy = state.Ly;
+          }
+          if (nKx == Ktx && nKy == Kty && nLx == Ltx && nLy == Lty)
+          {
+            sol = cost;
+            break;
+          }
+          if (visited[nKx][nKy][nLx][nLy][nPx][nPy]) continue;
+          visited[nKx][nKy][nLx][nLy][nPx][nPy] = true;
+          q2->push(State(nKx, nKy, nLx, nLy, nPx, nPy));
+        }
+        q1->pop();
+      }
+    }
+    printf("Case #%d: %d\n", t, sol);
+  }
+  return 0;
+}

statement/statues/sample.in

+3
+1 2 5 2 3 2
+1 1 1 3
+6 5 14
+##*##
+#####
+#####
+*###*
+*###*
+**#**
+0 0 2 2 1 1
+1 0 1 2
+3 3 2
+##*
+###
+*##
+2 0 2 1 0 2
+1 3 1 4
+5 5 40584
+**#**
+***##
+##***
+*****

statement/statues/sample.out

+Caso #1: 12
+Caso #2: 1
+Caso #3: -1