요즘 SRM 459 Hard를 풀고있는데, 잘 안풀리고있습니다. 아옳....(이후 문제에 대한 약간의 스포일이 등장할 수도 있습니다)
Network Flow를 써야 할 것 같은데, 여러 종류의 노드를 연결한 network를 구성해야 할 것 같았습니다. 이를테면,
source에서 N개의 point로 연결되고,
그 N개의 point에서는 NxM개의 point와 연결해야 하며,
마지막으로 그 NxM개의 point는 M개의 point와 연결하고,
마지막으로 M개의 point는 sink에 연결해야 하는
좀 복잡한 그래프라 도저히 머릿속에서 정점들의 라벨링이 힘들어졌습니다. 우와와아아아아아앙!
0 : source , 1 : sink, 2~N+1, N+2 ~ ... !@$!@#!@#
그래서 자동화했습니다.
template // NOX는 카테고리명입니다. 같은 값을 넣어줘야 같은 map을 쓰겠죠?
int build(const T &a) // 점의 parameter를 받아서 그 param에 해당하는 점이 있으면 리턴하고 없으면 만들어 리턴합니다.
{
static map aa; // 이 카테고리에서 만든 점들의 param->정점 Label의 map입니다.
if(aa.count(a)) return aa[a]; // 이미 param에 해당하는 점이 있으면 그걸 리턴합니다.
return aa[a] = addNode(); // addNode 함수는 새로운 정점을 생성해서 반환하는 함수입니다.
}
참 쉽죠? 사용법은 다음과 같습니다.
int main(void)
{
for(int i=0;i<10;i++)
{
cout << build<1>(i) << " ";
}
cout << endl;
for(int i=9;i>=0;i--)
{
cout << build<1>(i) << " ";
}
cout << endl;
cout << endl;
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
cout << build<2>(make_pair(i,j)) << " ";
}
cout << endl;
}
cout << endl;
for(int i=4;i>=0;i--)
{
for(int j=4;j>=0;j--)
{
cout << build<2>(make_pair(i,j)) << " ";
}
cout << endl;
}
}
여기서 초 주의해야 하는 버그가 있는데, build 함수의 NOX 값이 같아도 T 타입이 다른 경우에 서로 다른 aa를 사용하게 된다는 것입니다. 간단한 예로
build<2>(pair(3,5)) == build<2>(pair(3,5)) 이지만,
build<2>(pair(3,5)) != build<3>(pair(3,5)) 이고,(NOX값이 다르므로)
build<2>(pair(3,5)) != build<2>(pair(3,5)) 라는 것이죠.(T 형식이 달라지므로)
이 문제를 해결하려면 NOX값->typeinfo를 담는 map을 따로 global하게 만들면 될 것 같은데 그냥 조심해서 잘 쓰면 될 것 같아 안했습니다.
아니면 template를 쓰지 말고 프로그램 안에서 사용할 모든 type들을 직접 선언해주는 방법도 있겠죠.
int build1(int a) { /* 내용 / }
int build2(pair a) { / 거의 똑같은 내용 */ }