アリオンラインプログラミングテスト
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;
}
};