CSES. Police Chase

1.Problem

https://cses.fi/problemset/task/1695/

2.Idea

Find the max flow in the graph, and recover the minimum cut from the residual graph connectivity information.

3.Source

 int n, m;  
 Int adj[555][555];  
 Int oadj[555][555];  
 Int flow[555];  
 bool V[555];  
 int pa[555];  
 vector <pi> ans;  
 bool reachable() {  
      memset(V, false, sizeof V);  
      queue<int> Q;  
      Q.push(1); V[1] = 1;  
      while (!Q.empty()) {  
           int i = Q.front(); Q.pop();  
           RREP(j, n) if (adj[i][j] && !V[j]) {  
                V[j] = 1;  
                pa[j] = i;  
                Q.push(j);  
           }  
      }  
      return V[n];  
 }  
 void solve() {  
      cin >> n >> m;  
      RREP(i, n) RREP(j, n) adj[i][j] = oadj[i][j] = 0;  
      REP(i, m) {  
           Int a, b;  
           cin >> a >> b;  
           adj[a][b]++; adj[b][a]++;  
           oadj[a][b]++; oadj[b][a]++;  
      }  
      int v, u;  
      while (reachable()) {  
           Int flow = LINF;  
           for (v = n; v != 1; v = pa[v]) {  
                u = pa[v];  
                flow = min(flow, adj[u][v]);  
           }  
           for (v = n; v != 1; v = pa[v]) {  
                u = pa[v];  
                adj[u][v] -= flow;  
                adj[v][u] += flow;  
           }  
      }  
      reachable();  
      RREP(i, n) RREP(j, n) {  
           if (V[i] && !V[j] && oadj[i][j]) ans.push_back(pi(i, j));  
      }  
      cout << ans.size() << endl;  
      for (auto x : ans) cout << x.first << " " << x.second << endl;  
 }  

POJ.2135 Farm Tour

1.Problem
http://poj.org/problem?id=2135

2.Idea
Min cost flow

3.Source

 #define MAX_V 1005  
 #define INF 1000000000  
 struct edge{ int to, cap, cost, rev_index; };  
 int V;  
 vector<edge> G[MAX_V];  
 int dist[MAX_V];  
 int prevv[MAX_V], preve[MAX_V];  
 void add_edge(int from, int to, int cap, int cost){  
  G[from].push_back((edge){to, cap, cost, G[to].size()});  
  G[to].push_back((edge){from, 0, -cost, G[from].size() - 1});  
 }  
 int min_cost_flow(int s, int t, int f){  
  int res = 0;  
  while(f > 0){  
   fill(dist, dist + V, INF);  
   dist[s] = 0;  
   bool update = true;  
   while(update){  
    update = false;  
    for(int v = 0; v < V; v++){  
     if(dist[v] == INF) continue;  
     for(int i = 0; i < G[v].size(); i++){  
      edge &e = G[v][i];  
      if(e.cap > 0 && dist[e.to] > dist[v] + e.cost){  
       dist[e.to] = dist[v] + e.cost;  
       prevv[e.to] = v;  
       preve[e.to] = i;  
       update = true;  
      }  
     }  
    }  
   }  
   if(dist[t] == INF){  
    return -1;  
   }  
   int d = f;  
   for(int v = t; v != s; v = prevv[v]){  
    d = min(d, G[prevv[v]][preve[v]].cap);  
   }  
   f -= d;  
   res += d * dist[t];  
   for(int v = t; v != s; v = prevv[v]){  
    edge &e = G[prevv[v]][preve[v]];  
    e.cap -= d;  
    G[v][e.rev_index].cap += d;  
   }  
  }  
  return res;  
 }  
 int main(){  
  int N, M;  
  scanf("%d %d", &N, &M);  
  V = N;  
  while(M--){  
   int a, b, c;  
   scanf("%d %d %d", &a, &b, &c);  
   add_edge(a - 1, b - 1, 1, c);  
   add_edge(b - 1, a - 1, 1, c);  
  }  
  printf("%d\n", min_cost_flow(0, N - 1, 2));  
 }  

POJ.3469 Dual Core CPU

1.Problem
http://poj.org/problem?id=3469

2.Idea
Max Flow

3.Source

 #define MAX_V 20004  
 struct edge { int to, cap, rev; };  
 vector<edge> G[MAX_V];  
 int level[MAX_V];  
 int iter[MAX_V];  
 #define MAX_N 20004  
 #define MAX_M 200005  
 int N, M;  
 int A[MAX_N], B[MAX_N];  
 int a[MAX_M], b[MAX_M], w[MAX_M];  
 void add_edge(int from, int to, int cap)  
 {  
      edge e1, e2;  
      e1.to = to;  
      e1.cap = cap;  
      e1.rev = G[to].size();  
      G[from].push_back(e1);  
      e2.to = from;  
      e2.cap = 0;  
      e2.rev = G[from].size() - 1;  
      G[to].push_back(e2);  
 }  
 void bfs(int s)  
 {  
      memset(level, -1, sizeof level);  
      queue<int> que;  
      level[s] = 0;  
      que.push(s);  
      while (!que.empty()) {  
           int v = que.front(); que.pop();  
           for (int i = 0; i < G[v].size(); i++) {  
                edge &e = G[v][i];  
                if (e.cap > 0 && level[e.to] < 0) {  
                     level[e.to] = level[v] + 1;  
                     que.push(e.to);  
                }  
           }  
      }  
 }  
 int dfs(int v, int t, int f)   
 {  
      if (v == t) return f;  
      for (int &i = iter[v]; i < G[v].size(); i++) {  
           edge &e = G[v][i];  
           if (e.cap > 0 && level[v] < level[e.to]) {  
                int d = dfs(e.to, t, min(f, e.cap));  
                if (d > 0) {  
                     e.cap -= d;  
                     G[e.to][e.rev].cap += d;  
                     return d;  
                }  
           }  
      }  
      return 0;  
 }  
 //Dinic  
 int max_flow(int s, int t)  
 {  
      int flow = 0;  
      for (;;) {  
           bfs(s);  
           if (level[t] < 0) return flow;  
           memset(iter, 0, sizeof iter);  
           int f;  
           while ((f = dfs(s, t, INF)) > 0) {  
                flow += f;  
           }  
      }  
 }  
 void solve()  
 {  
      int s = N, t = s + 1;  
      for (int i = 0; i < N; i++) {  
           add_edge(i, t, A[i]);  
           add_edge(s, i, B[i]);  
      }  
      for (int i = 0; i < M; i++) {  
           add_edge(a[i] - 1, b[i] - 1, w[i]);  
           add_edge(b[i] - 1, a[i] - 1, w[i]);  
      }  
      printf("%d\n", max_flow(s, t));  
 }  
 int main() {  
      scanf("%d%d", &N, &M);  
      for (int i = 0; i < N; i++) {  
           scanf("%d%d", &A[i], &B[i]);  
      }  
      for (int i = 0; i < M; i++) {  
           scanf("%d%d%d", &a[i], &b[i], &w[i]);  
      }  
      solve();  
      return 0;  
 }  

POJ.3291 Dining

1.Problem
http://poj.org/problem?id=3281

2.Idea
Max Flow

3.Source

 #define MAX_V 500  
 int N, F, D;  
 struct edge { int to, cap, rev; };  
 vector<edge> G[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int from, int to, int cap)  
 {  
      edge e1, e2;  
      e1.to = to;  
      e1.cap = cap;  
      e1.rev = G[to].size();  
      G[from].push_back(e1);  
      e2.to = from;  
      e2.cap = 0;  
      e2.rev = G[from].size() - 1;  
      G[to].push_back(e2);  
 }  
 int dfs(int v, int t, int f)   
 {  
      if (v == t) return f;  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           edge &e = G[v][i];  
           if (!used[e.to] && e.cap > 0) {  
                int d = dfs(e.to, t, min(f, e.cap));  
                if (d > 0) {  
                     e.cap -= d;  
                     G[e.to][e.rev].cap += d;  
                     return d;  
                }  
           }  
      }  
      return 0;  
 }

//Ford-Fulkersen  
 int max_flow(int s, int t)  
 {  
      int flow = 0;  
      for (;;) {  
           memset(used, 0, sizeof used);  
           int f = dfs(s, t, INF);  
           if (f == 0) {  
                return flow;  
           }  
           flow += f;  
      }  
 }  
 int main() {  
      int N, F, D;  
      scanf("%d %d %d", &N, &F, &D);  
      for (int i = 0; i < F; i++) {  
           add_edge(0, 1 + i, 1);  
      }  
      for (int i = 0; i < N; i++) {  
           int Fi, Di;  
           scanf("%d %d", &Fi, &Di);  
           while (Fi--) {  
                int f;  
                scanf("%d", &f);  
                add_edge(1 + (f - 1), 1 + F + i, 1);  
           }  
           add_edge(1 + F + i, 1 + F + N + i, 1);  
           while (Di--) {  
                int d;  
                scanf("%d", &d);  
                add_edge(1 + F + N + i, 1 + F + N + N + (d - 1), 1);  
           }  
      }  
      for (int i = 0; i < D; i++) {  
           add_edge(1 + F + N + N + i, 1 + F + N + N + D, 1);  
      }  
      printf("%d\n", max_flow(0, 1 + F + N + N + D));  
 }  

POJ.1486 Sorting Slides

1.Problem
http://poj.org/problem?id=1486

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 2222  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 int N;  
 struct Rec {  
      int xmin, xmax, ymin, ymax;  
 } Recs[50004];  
 struct Point {  
      int x, y;  
 } Points[50004];  
 bool itIncludes(int i, int j)  
 {  
      if (  Recs[i].xmin < Points[j].x && Recs[i].xmax > Points[j].x  
           && Recs[i].ymin < Points[j].y && Recs[i].ymax > Points[j].y)   
           return true;  
      else   
           return false;  
 }  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int i = 0; i < N; i++) {  
           bool update = false;  
           for (int v = 0; v < V; v++) {  
                if (!used[v] && match[v] < 0) {  
                     int cnt = 0;  
                     int u = -1;  
                     for (int j = 0; j < G[v].size(); j++) {  
                          int f = G[v][j];  
                          if (!used[f]) {  
                               u = f;  
                               cnt++;  
                          }  
                     }  
                     if (cnt == 1) {  
                          update = true;  
                          match[v] = u;  
                          match[u] = v;  
                          used[v] = true;  
                          used[u] = true;  
                          res++;  
                     }  
                }  
           }  
           if (!update) break;  
      }  
      return res;  
 }  
 void solve()  
 {  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < N; i++) {  
           scanf("%d%d%d%d", &Recs[i].xmin, &Recs[i].xmax, &Recs[i].ymin, &Recs[i].ymax);  
      }  
      for (int i = 0; i < N; i++) {  
           scanf("%d%d", &Points[i].x, &Points[i].y);  
      }  
      V = 2 * N;  
      for (int i = 0; i < N; i++)  
           for (int j = 0; j < N; j++) {  
                if (itIncludes(i, j)) {  
                     add_edge(i, N + j);  
                }  
           }  
      if (bipartite_matching() > 0) {  
           for (int i = 0; i < N; i++) {  
                if (match[i] > 0) {  
                     printf("(%c,%d) ", 'A' + i, match[i] - N + 1);  
                }  
           }  
           printf("\n");  
      }  
      else {  
           printf("none\n");  
      }  
 }  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d", &N)>0) {  
           if (N == 0) break;  
           printf("Heap %d\n", t);  
           solve();  
           printf("\n");  
           t++;  
      }  
      return 0;  
 }  

POJ.2724 Purifying Machine

1.Problem
http://poj.org/problem?id=2724

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 2222  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 int N, M;  
 vector<string> vs;  
 bool isConnected(int i, int j)  
 {  
      int cnt = 0;  
      for (int k = 0; k < N; k++) {  
           if (vs[i][k] != vs[j][k]) cnt++;  
      }  
      return cnt == 1;  
 }  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      vs.clear();  
      for (int i = 0; i < M; i++) {  
           string s, t;  
           cin >> s;  
           t = s;  
           int j = 0;  
           for (j = 0; j < N; j++) {  
                if (s[j] == '*') break;  
           }  
           if (j < N) {  
                s[j] = '1';  
                t[j] = '0';  
                vs.push_back(s);  
                vs.push_back(t);  
           }  
           else {  
                vs.push_back(s);  
           }  
      }  
      sort(vs.begin(), vs.end());  
      vs.erase(unique(vs.begin(), vs.end()), vs.end());  
      V = vs.size();  
      for (int i = 0; i < V; i++)  
           for (int j = i + 1; j < V; j++) {  
                if (isConnected(i, j)) {  
                     add_edge(i, j);  
                }  
           }  
      printf("%d\n", V - bipartite_matching());  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &M)>0) {  
           if (N + M == 0) break;  
           solve();  
      }  
      return 0;  
 }  

POJ.3692 Kindergarten

1.Problem
http://poj.org/problem?id=3692

2.Idea
Reverse the graph and take Bipartite Matching

3.Source

 #define MAX_V 1000  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 bool g[500][500];  
 int GV, B, M;  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve(int t)  
 {  
      V = GV + B;  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < 500; i++)  
           for (int j = 0; j < 500; j++)  
                g[i][j] = 1;  
      for (int i = 0; i < M; i++) {  
           int k, t;  
           scanf("%d%d", &t, &k);  
           t = t - 1;  
           k = GV + k - 1;  
           g[t][k] = g[k][t] = 0;  
      }  
      for (int i = 0; i < GV; i++) {  
           for (int j = GV; j < V; j++) {  
                if (g[i][j]) add_edge(i, j);  
           }  
      }  
      printf("Case %d: %d\n", t, GV + B - bipartite_matching());  
 }  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d%d%d", &GV, &B, &M)>0) {  
           if (GV == 0) break;  
           solve(t);  
           t++;  
      }  
      return 0;  
 }  

POJ.1466 Girls and Boys

1.Problem
http://poj.org/problem?id=1466

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 1000  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < V; i++) {  
           int k, t;  
           scanf("%d: (%d)", &t, &k);  
           for (int j = 0; j < k; j++) {  
                scanf("%d", &t);  
                add_edge(i, t);  
           }  
      }  
      printf("%d\n", V - bipartite_matching());  
 }  
 int main()  
 {  
      while (scanf("%d", &V)>0) {  
           if (V == 0) break;  
           solve();  
      }  
      return 0;  
 }  

POJ.1274 The Perfect Stall

1.Problem
http://poj.org/problem?id=1274

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 1000  
 int V, N, M;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      V = N * 2;  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < N; i++) {  
           int k, t;  
           scanf("%d", &k);  
           for (int j = 0; j < k; j++) {  
                scanf("%d", &t);  
                add_edge(i, N + t - 1);  
           }  
      }  
      printf("%d\n", bipartite_matching());  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &M)>0) {  
           solve();  
      }  
      return 0;  
 }  

POJ.3057 Evacuation

1.Problem
http://poj.org/problem?id=3057

2.Idea
Bipartite Matching

3.Source

 struct P { int x, y; };  
 int dx[] = {0, 1, 0, -1};  
 int dy[] = {1, 0, -1, 0};  
 int X, Y;  
 char field[MAX_X][MAX_Y];  
 int dist[MAX_X][MAX_Y][MAX_X][MAX_Y];  
 vector<P> ds, ps;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int u, int v){  
  G[u].push_back(v);  
  G[v].push_back(u);  
 }  
 bool dfs(int v){  
  used[v] = true;  
  for(int i = 0; i < G[v].size(); i++){  
   int u = G[v][i];  
   int u_pair = match[u];  
   if(u_pair < 0 || !used[u_pair] && dfs(u_pair)){  
    match[v] = u;  
    match[u] = v;  
    return true;  
   }  
  }  
  return false;  
 }  
 void bfs(P door, int d[MAX_X][MAX_Y]){  
  queue<P> q;  
  d[door.x][door.y] = 0;  
  q.push(door);  
  while(!q.empty()){  
   P p = q.front(); q.pop();  
   for(int i = 0; i < 4; i++){  
    int nx = p.x + dx[i], ny = p.y + dy[i];  
    if(field[nx][ny] == '.' && d[nx][ny] < 0){  
     d[nx][ny] = d[p.x][p.y] + 1;  
     q.push((P){nx, ny});  
    }  
   }  
  }  
 }  
 void solve(){  
  int max_t = X * Y;  
  ds.clear(); ps.clear();  
  memset(dist, -1, sizeof(dist));  
  for(int i = 0; i < MAX_V; i++){  
   G[i].clear();  
  }  
  for(int x = 0; x < MAX_X; x++){  
   for(int y = 0; y < MAX_Y; y++){  
    if(field[x][y] == 'D'){  
     ds.push_back((P){x, y});  
     bfs((P){x, y}, dist[x][y]);  
    }else if(field[x][y] == '.'){  
     ps.push_back((P){x, y});  
    }  
   }  
  }  
  for(int i = 0; i < ds.size(); i++){  
   for(int j = 0; j < ps.size(); j++){  
    P d = ds[i], p = ps[j];  
    if(dist[d.x][d.y][p.x][p.y] >= 0){  
     for(int t = dist[d.x][d.y][p.x][p.y]; t <= max_t; t++){  
      add_edge((t - 1) * ds.size() + i, max_t * ds.size() + j);  
     }  
    }  
   }  
  }  
  if(ps.size() == 0){  
   printf("0\n");  
   return;  
  }  
  int num = 0;  
  memset(match, -1, sizeof(match));  
  for(int v = 0; v < max_t * ds.size(); v++){  
   memset(used, 0, sizeof(used));  
   if(dfs(v)){  
    if(++num == ps.size()){  
     printf("%d\n", v / ds.size() + 1);  
     return;  
    }  
   }  
  }  
  printf("impossible\n");  
 }  
 int main(){  
  int C;  
  scanf("%d", &C);  
  while(C--){  
   scanf("%d %d", &X, &Y);  
   memset(field, 'X', sizeof(field));  
   for(int i = 1; i <= X; i++){  
    scanf("%s", &field[i][1]);  
   }  
   solve();  
  }  
 }  

POJ.3041 Asteroids

1.Problem
http://poj.org/problem?id=3041

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 1000  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 #define MAX_K 10000  
 int N, K;  
 int R[MAX_K], C[MAX_K];  
 void solve()  
 {  
      V = N * 2;  
      for (int i = 0; i < K; i++) {  
           add_edge(R[i] - 1, N + C[i] - 1);  
      }  
      printf("%d\n", bipartite_matching());  
 }  
 int main()  
 {  
      scanf("%d%d", &N, &K);  
      for (int i = 0; i < K; i++) {  
           scanf("%d%d", &R[i], &C[i]);  
      }  
      solve();  
      return 0;  
 }