요즘 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<int NOX,typename T> // NOX는 카테고리명입니다. 같은 값을 넣어줘야 같은 map을 쓰겠죠?
int build(const T &a) // 점의 parameter를 받아서 그 param에 해당하는 점이 있으면 리턴하고 없으면 만들어 리턴합니다.
{
    static map<T,int> 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<int,int>(3,5)) == build<2>(pair<int,int>(3,5)) 이지만,

build<2>(pair<int,int>(3,5)) != build<3>(pair<int,int>(3,5)) 이고,(NOX값이 다르므로)

build<2>(pair<int,int>(3,5)) != build<2>(pair<int,long long>(3,5)) 라는 것이죠.(T 형식이 달라지므로)

이 문제를 해결하려면 NOX값->typeinfo를 담는 map을 따로 global하게 만들면 될 것 같은데 그냥 조심해서 잘 쓰면 될 것 같아 안했습니다.

아니면 template를 쓰지 말고 프로그램 안에서 사용할 모든 type들을 직접 선언해주는 방법도 있겠죠.

int build1(int a) { /* 내용 */ }

int build2(pair<int,int> a) { /* 거의 똑같은 내용 */ }