ACP Homework

highway.cc

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define MAXSITE 410

using namespace std;

int road[MAXSITE][MAXSITE];
vector<int> nb[MAXSITE];
int depth[MAXSITE];
int dp[MAXSITE][MAXSITE];
vector<int> depth2vetex[MAXSITE];

int getCount (int pre, int now, int next) {
    int count = 0;
    for (int i = 0; i < nb[next].size(); i++) {
        int other = nb[next][i];
        if (!road[other][pre] && !road[other][now] && !(other == now)) {
            count++;
        }
    }
//      printf("\t%d-%d-%d\t%d\n", pre, now, next, count);
    return count;
}

int main(int argc, const char *argv[]) {
    int n;
    cin >> n;
    while (n--) {
        // clean
        memset(road, 0, sizeof(int) * MAXSITE * MAXSITE);
        for (int i = 0; i < MAXSITE; i++) nb[i].clear();

        // input
        int S, R;
        cin >> S >> R;
        for (int i = 0; i < R; i++) {
            int a, b;
            cin >> a >> b;
            road[a][b] = 1;
            road[b][a] = 1;
            nb[a].push_back(b);
            nb[b].push_back(a);
        }

        // bfs
        for (int i = 0; i < MAXSITE; i++)
            depth[i] = -1;
        for (int i = 0; i < MAXSITE; i++)
            depth2vetex[i].clear();
        depth[0] = 0;
        depth2vetex[0].push_back(0);
        deque<int> q;
        q.push_back(0);
        while(q.size() > 0) {
            int now = q.front();
            q.pop_front();
            //              if (now == 1) break;
            for (int i = 0; i < nb[now].size(); i++) {
                int next = nb[now][i];
                if (depth[next] < 0) {
                    depth[next] = depth[now] + 1;
                    q.push_back(next);
                    depth2vetex[depth[next]].push_back(next);
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < MAXSITE; i++)
            for (int j = 0; j < MAXSITE; j++)
                dp[i][j] = -1;
        for (int i = 0; i < nb[0].size(); i++) {
            int next = nb[0][i];
            char mark[MAXSITE] = {0};
            int count = 0;
            for (int j = 0; j < nb[0].size(); j++) {
                if (!mark[nb[0][j]]) {
                    mark[nb[0][j]] = 1;
                    count++;
                }
            }
            for (int j = 0; j < nb[next].size(); j++) {
                if (!mark[nb[next][j]]) {
                    mark[nb[next][j]] = 1;
                    count++;
                }
            }
            dp[0][next] = count;
//              cout << "dp: 0" << ", " << next << "\t" << dp[0][next] << endl;
            if (next == 1) ans = max(ans, dp[0][next]);
        }
        for (int i = 1; i < depth[1]; i++) {
            for (int j = 0; j < depth2vetex[i].size(); j++) {
                for (int k = 0; k < depth2vetex[i+1].size(); k++) {
                    int now = depth2vetex[i][j];
                    int next = depth2vetex[i+1][k];
                    if (!road[now][next]) continue;
                    for (int x = 0; x < depth2vetex[i-1].size(); x++) {
                        int pre = depth2vetex[i-1][x];
                        if (!road[pre][now]) continue;
                        int count = getCount(pre, now, next);
                        dp[now][next] = max(dp[now][next], dp[pre][now] + count);
//                          cout << "dp: " << now << ", " << next << "\t" << dp[now][next] << endl;
                        if (next == 1) ans = max(ans, dp[now][next]);
                    }
                }
            }
        }
        cout << depth[1] << ' ' << ans - depth[1] - 1 << endl;
    }
    return 0;
}