アリオンラインプログラミングテスト

10587 ワード

プログラミングテストは規定の時間内にできなかったし、素質テストも冷めてしまったが、後で打ったコードを置いて、どれだけのサンプルを过ごすことができるか分からない.問題は、1行目に2つの数値を入力し、1行目はシステム個数を表し、2行目はシステム間の依存関係を表す.次に、各システムの消費電力を入力し、スペースで区切ります.最後に、各システム間の依存関係を入力します.最大の消費時間総量を算出する必要がある.(最長チェーンか最大消費時間総量かは覚えていません)
例:
5 4
7 //1 7ms
5 //2 5ms
3 // ...
5
6
1 2 //1 2 
1 3 //1 3 
2 5 //2 5 
4 5 //4 5 
 1->2->5,  1->3,  4->5
#include
using namespace std;
class Solution {
public:
    // , 
    void dfs(int **matrix, bool* visited, int* cost, int point, int count, int& costs, int& ans) {
        if (!visited[point]) {
            visited[point] = true;
            for (int i = 1; i <= count; i++) {
                if (i != point && !visited[i] && matrix[point][i]) {
                    costs += cost[i];
                    // 
                    if (ans < costs) ans = costs;
                    dfs(matrix, visited, cost, i, count, costs, ans);
                    costs -= cost[i];
                }
            }
        }
    }
    void solution() {
        int count_system, count_dep;
        // 
        cin >> count_system >> count_dep;

        // 
        int* cost = new int[count_system+1];

        // 
        int** matrix = new int*[count_system+1];
        bool* visited = new bool[count_system + 1];

        for (int i = 0; i < count_system+1; i++) {
            matrix[i] = new int[count_system+1];
            for (int j = 0; j < count_system+1; j++) {
                matrix[i][j] = 0;
            }
        }
        // 
        for (int i = 1; i < count_system+1; i++) {
            cin >> cost[i];
        }
        for (int i = 0; i < count_dep; i++) {
            int start, end;
            cin >> start >> end;
            matrix[start][end] = 1;
        }
        int ans = 0;
        for (int i = 0; i < count_system; i++) {
            for (int i = 0; i < count_system + 1; i++) {
                visited[i] = false;
            }
            dfs(matrix, visited, cost, i + 1, count_system, cost[i+1], ans);
        }
        cout << ans << endl;

    }
};

int main() {
    Solution s;
    s.solution();
    system("pause");
}

/** 
** 
** 
**/

class Solution2 {
public:
    void dfs(int **matrix, bool* visited, int* cost, int point, int count, int length, int& longest, int costs, int& ans) {
        if (!visited[point]) {
            visited[point] = true;
            for (int i = 1; i <= count; i++) {
                if (i != point && !visited[i] && matrix[point][i]) {
                    costs += cost[i];
                    length += 1;
                    // 
                    if (longest < length) {
                        longest = length;
                        ans = costs;
                    }
                    dfs(matrix, visited, cost, i, count, length, longest, costs, ans);
                    costs -= cost[i];
                }
            }
        }
    }
    void solution() {
        int count_system, count_dep;
        cin >> count_system >> count_dep;
        int* cost = new int[count_system+1];
        int** matrix = new int*[count_system+1];
        bool* visited = new bool[count_system + 1];
        for (int i = 0; i < count_system+1; i++) {
            matrix[i] = new int[count_system+1];
            visited[i] = false;
            for (int j = 0; j < count_system+1; j++) {
                matrix[i][j] = 0;
            }
        }

        for (int i = 1; i < count_system+1; i++) {
            cin >> cost[i];
        }
        for (int i = 0; i < count_dep; i++) {
            int start, end;
            cin >> start >> end;
            matrix[start][end] = 1;
        }
        int ans = 0;
        int length = 0;
        for (int i = 0; i < count_system; i++) {
            for (int i = 0; i < count_system + 1; i++) {
                visited[i] = false;
            }
            dfs(matrix, visited, cost, i + 1, count_system, 0, length, cost[i + 1], ans);
        }
        cout << ans << endl;

    }
};