Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Apr 29th, 2012  |  syntax: None  |  size: 3.62 KB  |  hits: 9  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. #include <algorithm>
  5. #include <cstring>
  6. #include <cstdlib>
  7. #include <cstdio>
  8. #define MAXSITE 410
  9.  
  10. using namespace std;
  11.  
  12. int road[MAXSITE][MAXSITE];
  13. vector<int> nb[MAXSITE];
  14. int depth[MAXSITE];
  15. int dp[MAXSITE][MAXSITE];
  16. vector<int> depth2vetex[MAXSITE];
  17.  
  18. int getCount (int pre, int now, int next) {
  19.     int count = 0;
  20.     for (int i = 0; i < nb[next].size(); i++) {
  21.         int other = nb[next][i];
  22.         if (!road[other][pre] && !road[other][now] && !(other == now)) {
  23.             count++;
  24.         }
  25.     }
  26. //      printf("\t%d-%d-%d\t%d\n", pre, now, next, count);
  27.     return count;
  28. }
  29.  
  30. int main(int argc, const char *argv[]) {
  31.     int n;
  32.     cin >> n;
  33.     while (n--) {
  34.         // clean
  35.         memset(road, 0, sizeof(int) * MAXSITE * MAXSITE);
  36.         for (int i = 0; i < MAXSITE; i++) nb[i].clear();
  37.  
  38.         // input
  39.         int S, R;
  40.         cin >> S >> R;
  41.         for (int i = 0; i < R; i++) {
  42.             int a, b;
  43.             cin >> a >> b;
  44.             road[a][b] = 1;
  45.             road[b][a] = 1;
  46.             nb[a].push_back(b);
  47.             nb[b].push_back(a);
  48.         }
  49.  
  50.         // bfs
  51.         for (int i = 0; i < MAXSITE; i++)
  52.             depth[i] = -1;
  53.         for (int i = 0; i < MAXSITE; i++)
  54.             depth2vetex[i].clear();
  55.         depth[0] = 0;
  56.         depth2vetex[0].push_back(0);
  57.         deque<int> q;
  58.         q.push_back(0);
  59.         while(q.size() > 0) {
  60.             int now = q.front();
  61.             q.pop_front();
  62.             //              if (now == 1) break;
  63.             for (int i = 0; i < nb[now].size(); i++) {
  64.                 int next = nb[now][i];
  65.                 if (depth[next] < 0) {
  66.                     depth[next] = depth[now] + 1;
  67.                     q.push_back(next);
  68.                     depth2vetex[depth[next]].push_back(next);
  69.                 }
  70.             }
  71.         }
  72.  
  73.         int ans = -1;
  74.         for (int i = 0; i < MAXSITE; i++)
  75.             for (int j = 0; j < MAXSITE; j++)
  76.                 dp[i][j] = -1;
  77.         for (int i = 0; i < nb[0].size(); i++) {
  78.             int next = nb[0][i];
  79.             char mark[MAXSITE] = {0};
  80.             int count = 0;
  81.             for (int j = 0; j < nb[0].size(); j++) {
  82.                 if (!mark[nb[0][j]]) {
  83.                     mark[nb[0][j]] = 1;
  84.                     count++;
  85.                 }
  86.             }
  87.             for (int j = 0; j < nb[next].size(); j++) {
  88.                 if (!mark[nb[next][j]]) {
  89.                     mark[nb[next][j]] = 1;
  90.                     count++;
  91.                 }
  92.             }
  93.             dp[0][next] = count;
  94. //              cout << "dp: 0" << ", " << next << "\t" << dp[0][next] << endl;
  95.             if (next == 1) ans = max(ans, dp[0][next]);
  96.         }
  97.         for (int i = 1; i < depth[1]; i++) {
  98.             for (int j = 0; j < depth2vetex[i].size(); j++) {
  99.                 for (int k = 0; k < depth2vetex[i+1].size(); k++) {
  100.                     int now = depth2vetex[i][j];
  101.                     int next = depth2vetex[i+1][k];
  102.                     if (!road[now][next]) continue;
  103.                     for (int x = 0; x < depth2vetex[i-1].size(); x++) {
  104.                         int pre = depth2vetex[i-1][x];
  105.                         if (!road[pre][now]) continue;
  106.                         int count = getCount(pre, now, next);
  107.                         dp[now][next] = max(dp[now][next], dp[pre][now] + count);
  108. //                          cout << "dp: " << now << ", " << next << "\t" << dp[now][next] << endl;
  109.                         if (next == 1) ans = max(ans, dp[now][next]);
  110.                     }
  111.                 }
  112.             }
  113.         }
  114.         cout << depth[1] << ' ' << ans - depth[1] - 1 << endl;
  115.     }
  116.     return 0;
  117. }
create a new version of this paste RAW Paste Data