Решение задачи "Теория игр" с Acmp

Без пояснения   Просмотров: 20

Одним из интересных объектов, изучаемых в теории игр, являются так называемые антагонистические игры двух лиц. Такие игры характеризуются множеством X стратегий первого игрока, множеством Y стратегий второго игрока и функцией выигрыша K(x, y) (x из X, y из Y). Если множества стратегий X и Y конечны, то такую игру принято называть матричной, так как функцию выигрыша K в этом случае удобно задавать матрицей.

Рассмотрим матричную игру, в которой X = {1,…,n}, Y = {1,…,m}. Матрицу выигрышей обозначим символом K. Нижним значением игры назовем число maxi=1..nminj=1..m Kij . Верхним значением игры назовем число minj=1..mmaxi=1..n Kij. Отметим также, что игры, у которых нижнее и верхнее значение совпадают, называются играми с седловой точкой.

Задана матрица выигрышей K для некоторой матричной игры. Найдите ее верхнее и нижнее значение.

Код 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m, mx;
    cin >> n >> m;
    vector<int> res1;
    vector<int> res2;
    vector< vector<int> > a;
    for(int i = 0; i < n; ++i){
        vector<int> t(m);
        int mn = INFINITY;
        for(int j = 0; j < m; ++j){
            cin >> t[j];
            mn = min(mn, t[j]);
        }
        res1.push_back(mn);
        a.push_back(t);
    }
    sort(res1.begin(), res1.end());


    for(int i = 0; i < m; ++i){
        int mx = INT_MIN;
        for(int j = 0; j < n; ++j)
            mx = max(a[j][i], mx);
        res2.push_back(mx);
    }
    sort(res2.begin(), res2.end());
    cout << res1[res1.size() - 1] << ' ' <<  res2[0];
    return 0;
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться