1005) acm짓기

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

#define VERTEXMAX 1001
#define EDGEMAX 100001
vector<int> condition[VERTEXMAX];

int vertex; 
int edge;

void Find(int finder, int *should_be_built, int *time, int *result)
{
queue<int> q;
fill(result, result + VERTEXMAX, 0);

for (int p = 0; p < vertex; p++)
{
if (should_be_built[p] == 0)
{
q.push(p); 
break;
}
}
printf("shoud %d", should_be_built[finder]);
while (should_be_built[finder] > 0)
{
int pusher = q.front();
printf("pusher %d\n", pusher);
q.pop();

for (int next : condition[pusher])
{
result[next] = max(result[next], result[pusher] + time[pusher]);
should_be_built[next]--;
if (should_be_built[next] == 0)
q.push(next);
}
}
}

void input(int *should_be_built, int *time)
{
cin >> vertex; //cin = scanf
cin >> edge; //간선(조건) 개수

for (int i = 0; i < vertex; i++)
{
scanf_s("%d", time + i, sizeof(time + i)); //요구시간 배열에 저장 ㄹ
}

for (int i = 0; i < edge; i++)
{
int from, to;
scanf_s("%d", &from, sizeof(from));
scanf_s("%d", &to, sizeof(to));

condition[from - 1].push_back(to - 1);
should_be_built[to - 1]++;
}
}

int main()
{
int should_be_built[VERTEXMAX];
int time[VERTEXMAX];
int result[VERTEXMAX];

fill(should_be_built, should_be_built + VERTEXMAX, 0);
fill(time, time + VERTEXMAX, 0);

int howmany;
cin >> howmany;

for (int p = 0; p < howmany; p++)
{
input(should_be_built, time);
int finder;
cin >> finder;
finder--;

Find(finder, should_be_built, time, result);
printf("%d\n", result[finder] + time[finder]);
}
system("pause");
return 0;
}

////////////////////////////////////////////////

 

기본 알고리즘

 

input에서, 각 정점에 맞는 시간과 from, to를 저장후, from 벡터에 to들을 저장

should_be_built에는 to를 건설하는데 필요한 크래프트 개수 저장

 

Find에서, 필요한 크래프트 개수가 0인 첫 시작점을 큐로 넣고, pop해서 시작점으로 삼는다

 

이 시작점의 벡터 내에 저장된 정점을 하나씩 방문. 이때마다 해당 정점의 should_be_built를 하나씩 감소. 만일 0이 됐다면 큐에 저장.

거리 배열 result에는 기존의 것과 새로 갱신된 것 중 큰 것을 삽입.

큐는, 따라서 건설이 완료된(건설 조건을 충족한) 건물들이 지속적으로 push되며, 이들 중 만일 기존 시간에 비해 적은 것이 있다면 무시한다.

 

최종 결과는, find의 값 + finder의 걸리는 시간