[그래프] [시도 x] MATCHFIX 승부 조작

1. 문제

 

N명의 선수를 승부 조작에 참여시켰다.

 

결승 리그는 여러번의 1:1 경기이다

 

무승부 없이 항상 승부가 나며

 

모든 경기가 끝난 후 승수가 가장 많은 선수가 우승한다.

 

만약 가장 승수가 많은 선수가 둘 이상 있을 겨우 공동 우승을 하게 된다

 

 

대부분 우승하지 못할 것으로 여겨지는 X 를 단독 우승하도록해서 이득을 취하려고한다

 

의심을 피하기위해 가능한 X가 적은 승수로 우승하도록 하고싶다

 

현재 각 선수의 승수와 남아 있는 경기 목록이 주어질 때.

 

승부를 적절히 조작해 X가 우승하도록 할 수 있는지 여부를 계산하고,

 

우승할 수 있다면 필요한 X의 최소 승수는 얼마인지 계산하는 프로그램을 작성하여라.

 

 

이때 단독 우승이 불가능할 경우 -1을 출력한다.

 

그리고 모든 선수가 같은 수의 경기를 치르도록 보장되어 있지 않는다.                                             

 

2. 책의 풀이

유량 네트워크 만들기

 

0번 선수가 총 w승으로 단독 우승하기 위해서는 다음 두 가지 조건이 모두 성립해야한다.

 

1. 0번 선수가 남은 경기를 전부 승리했다고 가정했을 때 w승 이상을 할 수 있어야한다.

2. 남은 경기의 승패가 적절히 결정되어 다른 선수들은 모두 w -1 승 이하로 리그를 마칠 수 있어야한다.

 

이 두 조건을 만족해야하는 것과 이 문제가 자원 배분 문제임을 알아채 적절히 그래프를 만들고,

 

포드-풀커슨 알고리즘을 사용하면 문제를 해결할 수 있다.

 

3. 2번 조건 만족시키기

2번 조건인

 

0번선수를 제외하고 모든 선수가 w-1승이하가 되어야한다는 것

 

을 만족시키기 이전에 그래프를 표현하는 방법부터 정해야한다.

 

 

이 문제는 '승'이라는 자원을 배분하는 문제이다.

 

그러므로 '경기'들 정점으로 보내는 1승을 보내는  '소스'와 

 

각 선수들이 받은 승들을 받는 '싱크' 를 따로 생성해야한다.

 

 

또한 이 자원의 총 개수는 '남은 경기수 + 현재 승수의 합' 이 되어야한다.

 

하지만 현재 승수의 합은 고정적이므로 '남은 경기수' 만 생각하면 된다.

 

여기서 0을제외한 모든 선수가 w-1승 이하가 되어야하므로 

 

capacity[i + m + 2][1] = (w-1 - win[i]) 

(0: 소스 , 1: 싱크, win[i]: i번 선수의 현재 승수,  0 + m+2: 그래프상에서 0 번 선수의 인덱스 )

 

위 식이 선수에서 싱크로가는 용량이 된다면 항상 w-1이하 ( 0번은 w) 가 된다.

 

 

그러므로 만약 

 

소스 - 1 - 경기

 

경기 -1- 선수a

           - 선수b

선수- c - 싱크

 

같은 형태의 그래프에 포드-풀커슨 알고리즘을 적용하고 결과값이 m이 된다면

 

이는 모든 선수의 승수를 w-1이하로 만들 수 있다는게 된다.

 

 

4. 1번 조건 만족시키기

1번 조건은 0번이 w가 될 수 있는지를 확인하면 된다.

 

하지만 이는 bfs탐색을 항상 0 번부터 채워 넣으면 

 

입력단에서 0을 포함한 경기수 x를 센다음

 

 win[0] <= w <= win[0] + x 

 

의 범위만 조사하면 자연스럽게 만족된다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
 
using namespace std;
 
const int INF = 987654321;
int V, n, m, totalCount, xmatch;
 
vector<vector<int> > capacity;
vector<int> currentWin;
vector<pair<int, int> > match;
vector<vector<int> > flow;
 
 
int networkFlow(int src, int sink)
{
    while(true)
    {
        queue<int> q;
        vector<int> parent = vector<int>(V, -1);
        parent[src] = src;
        q.push(src);
        while(!q.empty() && parent[sink] == -1)
        {
            int here = q.front(); q.pop();
            for(int there = 0; there < V; there++)
            {
                if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1)
                {
                    q.push(there);
                    parent[there] = here;
                }
            }
        }
        if(parent[sink] == -1) break;
        int cost = INF;
        for(int i = sink; i != src; i = parent[i])
            cost = min(cost, capacity[parent[i]][i] - flow[parent[i]][i]);
        for(int i = sink; i != src; i = parent[i])
        {
            flow[i][parent[i]] -= cost;
            flow[parent[i]][i] += cost;
        }
        totalCount += cost;
    }
    return totalCount;
}
 
 
bool isCanWin(int w)
{
    for(int i = 0 ; i < n ; i++){
        capacity[i + m + 2][1] = ((i == 0 ? w: w-1) - currentWin[i]);
        if(capacity[i+m+2][1] < 0) return false;
    }
    return (networkFlow(0, 1) == m);
}
 
 
int solve()
{
    int ret = -1;
    capacity = vector<vector<int> > (V , vector<int>(V, 0));
    flow = vector<vector<int> >(V, vector<int>(V, 0));
 
    for(int i = 0; i < m ; i++)
    {
        capacity[0][i+2] = 1;
        capacity[i+2][m + 2 + match[i].first] = 1;
        capacity[i+2][m + 2 + match[i].second] = 1;
    }
 
    for(int i = currentWin[0]; i <= currentWin[0] + xmatch ; i++)
        if(isCanWin(i))
            return i;
    return ret;
}
 
 
int main()
{
    int C;
    cin>>C;
    while(C--)
    {
        cin>>n>>m;
        currentWin = vector<int>(n, 0);
        match = vector<pair<int, int> > (m);
        xmatch = 0;
        totalCount = 0;
        V = n + m + 2;
        for(int i = 0; i < n; i++)
            cin>>currentWin[i];
        for(int i = 0; i < m; i++)
        {
            int a, b;
            cin>>a>>b;
            match[i] = make_pair(a, b);
            if(a == 0 || b == 0)
                xmatch++;
        }
        cout<<solve()<<"\n";
    }
}

 

 

www.algospot.com/judge/problem/read/MATCHFIX