개발자 톡
로드 밸런서 트래픽 예측 C++ 반례부탁드립니다.
- 등록일
- 2024-01-20 19:02:32
- 조회수
- 208
- 작성자
- hys339631
#include <iostream>
#include <vector>
#include <queue>
#define MAX_SIZE 100004
using namespace std;
struct Node{
long long tN;
vector<long long> v;
};
long long N,K;
Node LB[MAX_SIZE];
long long ret[MAX_SIZE];
long long in_degree[MAX_SIZE];
queue<long long> q;
void display_() {
for(long long i=1;i<=N;i++) {
cout << ret[i] << " ";
}
cout << '\n';
}
void check_(long long idx) {
bool check_Flag=false;
if(LB[idx].tN<ret[idx]) {
check_Flag=true;
}
for(long long i=0;i<LB[idx].tN;i++) {
if(check_Flag) {
in_degree[LB[idx].v[i]]-=1;
if(in_degree[LB[idx].v[i]]==0) {
q.push(LB[idx].v[i]);
}
}
ret[LB[idx].v[i]]+=ret[idx]/LB[idx].tN;
}
for(long long i=0;i<ret[idx]%LB[idx].tN;i++) {
if(!check_Flag) {
in_degree[LB[idx].v[i]]-=1;
if(in_degree[LB[idx].v[i]]==0) {
q.push(LB[idx].v[i]);
}
}
ret[LB[idx].v[i]]+=1;
}
}
void go_() {
ret[1]=K;
q.push(1);
while(!q.empty()) {
long long temp=q.front();
q.pop();
if(LB[temp].tN!=0) {
check_(temp);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> K;
for(long long i=1;i<=N;i++) {
long long tempN;
cin >> tempN;
LB[i].tN=tempN;
for(long long j=0;j<tempN;j++) {
long long data;
cin >> data;
LB[i].v.push_back(data);
in_degree[data]+=1;
}
}
go_();
display_();
return 0;
}
위상정렬을 사용해서 in_degree 가 0 인 node 의 자식들에게 값을 분배하는 식으로 알고리즘을 작성했는데 반례가 도저히 생각나지 않습니다,..