가장 큰 흐름에 흥미를 느끼는 계기가 되는 문제다.

제목의 뜻

가위바위보.스크레이퍼가 있습니다(G, S, P).

에는 A와 B가 있어 n차례 경기를 치른다.각각 Ag, As, Ap, Bg, Bs, Bp를 꺼낸다.(n경기이기 때문에 쌍방의 합은 n이다)

애자는 무승부다.

A가 이긴 최대 수량과 최소 수량

을 대답했다.

생각

우선 문제를 다음과 같이 바꾸자.

A가 이긴 최대 수량과 최소 수량

을 대답했다.

A가 이긴 최대 수량과'n에서 애인에게 질 수 있는 최대 수량을 뺀다'

두 개의 도표를 만들면 다음과 같다.

포인트는 각 손 옆의 캡이 무한대라는 것이다.(본 문제에서 각종 수량을cap로 할 수 있으나 문제로 고려할 때cap를 제한할 필요가 없고 inf로 처리할 수 있다)
우선 왼쪽 승리의 최대 승리 횟수를 계산한 도표다.

0,7을 기점으로 하고 다른 노드는 그림에서 보듯이 각 손 노드

시작지점에서 A의 각 노드에cap=발급수속

마찬가지로 B의 각 노드에서cap=를 꺼낸 손으로 스트레칭

A는 우승 그룹의 손(A자는 B자 가위 등)에 테두리를 붙였는데 이 캡은 무한대였다.

s에서 t까지의 최대 유량은 A가 이길 수 있는 최대 수량이다.
다음은 오른쪽에 가장 큰 실패자 수를 구하는 도표입니다.

도표의 구성은 같다.

A, B 사이의 스티커 방법은 다르다. A는 사랑하거나 지는 손(A고라면 B고 또는 B보)에 테두리를 붙이는데 이cap은 무한대이다.

s에서 t까지의 최대 흐름 mf는 A의'가장 지거나 사랑하는 수'다.따라서 n-mf는 A가 이긴 최소 수량이다.

이루어지다

ACL 부분은 생략됩니다.

int main(int argc, char *argv[]) {
    mf_graph<ll> mfwin(8);
    mf_graph<ll> mflose(8);
    ll n,ar,as,ap,br,bs,bp;
    cin>>n>>ar>>as>>ap>>br>>bs>>bp;
    ll inf = 1e12;
    ll reswin, reslose;

    // 勝つ回数
    mfwin.add_edge(0, 1, ar); mfwin.add_edge(0, 2, as); mfwin.add_edge(0, 3, ap);
    mfwin.add_edge(4, 7, br); mfwin.add_edge(5, 7, bs); mfwin.add_edge(6, 7, bp);
    mfwin.add_edge(1, 5, inf);
    mfwin.add_edge(2, 6, inf);
    mfwin.add_edge(3, 4, inf);
    reswin = mfwin.flow(0, 7);
    // あいこ　か　まけ　の回数
    mflose.add_edge(0, 1, ar); mflose.add_edge(0, 2, as); mflose.add_edge(0, 3, ap);
    mflose.add_edge(4, 7, br); mflose.add_edge(5, 7, bs); mflose.add_edge(6, 7, bp);
    mflose.add_edge(1, 4, inf); mflose.add_edge(1, 6, inf);
    mflose.add_edge(2, 4, inf); mflose.add_edge(2, 5, inf);
    mflose.add_edge(3, 5, inf); mflose.add_edge(3, 6, inf);
    reslose = mflose.flow(0, 7);

    cout << n - reslose << " " << reswin << "\n";
}