CodeForces. 1337C Linova and Kingdom

1.Problem
https://codeforces.com/contest/1337/problem/C

2.Idea
Sort by {Depth - Child Number}, and pick k vertices.

3.Source

 int n, k;  
 vector<int> adj[N];  
 int dist[N];  
 bool visited[N];  
 int child[N];  
 bool col[N];  
 int dist2[N];  
 struct City {  
      int num, child, dist;  
      bool operator < (const City &a)const {  
           return dist - child < a.dist - a.child;  
      }  
 } Cities[N];  
 void getChild(int k)  
 {  
      //cout << k << endl;  
      visited[k] = true;  
      for (int i = 0; i < adj[k].size(); i++) {  
           int u = adj[k][i];  
           if (visited[u] == 0) {  
                getChild(u);  
                child[k] += (1 + child[u]);  
           }  
      }  
 }  
 void colorCities()  
 {  
      for (int i = 0; i < n; i++) {  
           Cities[i].num = i;  
           Cities[i].child = child[i];  
           Cities[i].dist = dist[i];  
      }  
      sort(Cities, Cities + n);  
      for (int i = 0; i < n - k; i++) {  
           int t = Cities[i].num;  
           col[t] = true;  
      }  
 }  
 int main()  
 {  
      cin >> n >> k;  
      for (int i = 0; i < n - 1; i++) {  
           int u, v;  
           cin >> u >> v;  
           u--; v--;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      // get dist  
      memset(visited, 0, sizeof visited);  
      queue<P> q;  
      q.push(P(0, 0));  
      while (!q.empty()) {  
           int v = q.front().first;  
           int d = q.front().second;  
           q.pop();  
           visited[v] = 1;  
           dist[v] = d;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0 && dist[u] == 0) {  
                     q.push(P(u, d + 1));  
                }  
           }  
      }  
      //get child  
      memset(visited, 0, sizeof visited);  
      getChild(0);  
      //color  
      colorCities();  
      //count  
      memset(visited, 0, sizeof visited);  
      queue<P> q1;  
      q1.push(P(0, 0));  
      while (!q1.empty()) {  
           int v = q1.front().first;  
           int d = q1.front().second;  
           q1.pop();  
           visited[v] = 1;  
           dist2[v] = d;  
           if (col[v]) d++;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0) {  
                     q1.push(P(u, d));  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (col[i] == 0) ans += dist2[i];  
      }  
      cout << ans << endl;  
      return 0;  
 }  

CodeForces. 1339D Edge Weight Assignment

1.Problem.
https://codeforces.com/contest/1339/problem/D

2.Idea
Here

3.Source

 vector<int> adj[N];  
 int d[N];  
 set<int> st;  
 // calc dist from root  
 void dfs(int v, int p)  
 {  
      for (auto& x : adj[v]) {  
           if (x == p) continue;  
           d[x] = d[v] + 1;  
           dfs(x, v);  
      }  
 }  
 int main()  
 {  
      int n;  
      cin >> n;  
      for (int i = 1; i < n; i++) {  
           int v, u;  
           cin >> v >> u;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      int root = 0;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                root = i;  
                break;  
           }  
      }  
      dfs(root, 0);  
      int mn = 1, mx = n - 1;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                if (d[i] % 2 != 0) {  
                     mn = 3;  
                }  
                st.insert(adj[i][0]);  
                --mx;  
           }  
      }  
      mx += st.size();  
      cout << mn << " " << mx << endl;  
      return 0;  
 }  

POJ. 3009 Curling 2.0

Problem:
http://poj.org/problem?id=3009

Idea:
Looking for the minimum answer in 10 steps by dfs. When the stone reach to goal, it has to stop the search (In the code the 'flag' is for this purpose).

Source:

 int f[22][22];  
 int h, w;  
 int sx, sy, gx, gy;  
 int ans = 100;  
 void dfs(int x, int y, int throws)  
 {  
      if (throws >= 10) return;  
      int xx = x;  
      int yy = y;  
      int flag = 0;  
      //up  
      x = xx;  
      y = yy;  
      flag = 0;  
      while (x >=0 && f[x][y] == 0) {  
           if (x == gx && y == gy) {  
                ans = min(throws + 1, ans);  
                flag = 1;  
                break;  
           }  
           x--;  
      }  
      if (flag==0 && x >= 0 && (x +1) != xx) {  
           x++;  
           f[x - 1][y] = 0;  
           dfs(x, y, throws + 1);  
           f[x - 1][y] = 1;  
      }  
      //down  
      x = xx;  
      y = yy;  
      flag = 0;  
      while (x < h && f[x][y] == 0) {  
           if (x == gx && y == gy) {  
                ans = min(throws + 1, ans);  
                flag = 1;  
                break;  
           }  
           x++;  
      }  
      if (flag == 0 && x < h && (x - 1) != xx) {  
           x--;  
           f[x+1][y] = 0;  
           dfs(x, y, throws + 1);  
           f[x+1][y] = 1;  
      }  
      //right  
      x = xx;  
      y = yy;  
      flag = 0;  
      if (x == 2 && y == 1) {  
           int g = 0;  
      }  
      while (y < w && f[x][y] == 0) {  
           if (x == gx && y == gy) {  
                ans = min(throws + 1, ans);  
                flag = 1;  
                break;  
           }  
           y++;  
      }  
      if (flag == 0 && y < w && (y -1) != yy) {  
           y--;  
           f[x][y + 1] = 0;  
           dfs(x, y, throws + 1);  
           f[x][y + 1] = 1;  
      }  
      //left  
      x = xx;  
      y = yy;  
      flag = 0;  
      while (y >= 0 && f[x][y] == 0) {  
           if (x == gx && y == gy) {  
                ans = min(throws + 1, ans);  
                flag = 1;  
                break;  
           }  
           y--;  
      }  
      if ( flag == 0 && y >= 0 && (y+1) != yy) {  
           y++;  
           f[x][y - 1] = 0;  
           dfs(x, y, throws + 1);  
           f[x][y - 1] = 1;  
      }  
      return;  
 }  
 int main()  
 {  
      while (1) {  
           cin >> w >> h;  
           if (w + h == 0) break;  
           ans = 100;  
           for (int i = 0; i<h; i++)  
                for (int j = 0; j < w; j++) {  
                     cin >> f[i][j];  
                     if (f[i][j] == 2) {  
                          sx = i;  
                          sy = j;  
                          f[i][j] = 0;  
                     }  
                     if (f[i][j] == 3) {  
                          gx = i;  
                          gy = j;  
                          f[i][j] = 0;  
                     }  
                }  
           dfs(sx, sy, 0);  
           if (ans < 100) cout << ans << endl;  
           else cout << -1 << endl;  
      }  
      return 0;  
 }  

POJ.3050 Hopscotch

Problem:
http://poj.org/problem?id=3050

Idea:
Using dfs for exhaustive search.

Source:

 #include<cstdio>  
 #include<queue>  
 #include<string>  
 #include<iostream>  
 #include<vector>  
 #include<set>  
 using namespace std;  
 char g[5][5];  
 set<string> ans;  
 int dx[5] = { 0,0,-1,1};  
 int dy[5] = { -1,1,0,0};  
 void dfs(int i, int j, string res, int cur)  
 {  
      if (cur == 6) {  
           ans.insert(res);  
           return;  
      }  
      for (int k = 0; k < 4; k++) {  
           int nx = i + dx[k];  
           int ny = j + dy[k];  
           if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 ) {  
                dfs(nx, ny, res + g[nx][ny], cur + 1);  
           }  
      }  
      return;  
 }  
 int main()  
 {  
      for (int i = 0; i < 5; i++)  
           for (int j = 0; j < 5; j++) {  
                //scanf("%c", &g[i][j]);  
                cin >> g[i][j];  
           }  
      for (int i = 0; i < 5; i++)  
           for (int j = 0; j < 5; j++) {  
                dfs(i, j, "", 0);  
           }  
      cout << ans.size() << endl;  
      return 0;  
 }