Giả sử nếu ta muốn 1 người A vô địch, thì mọi trận anh ta chưa đấu, ta sẽ xem như anh ta sẽ thắng

Gọi:

p[i] = điểm hiện tại (không tính trận chưa đấu) của người thứ i

mx[i] = điểm lớn nhất mà người i có thể đạt được (giả sử người này thắng mọi trận)

Nếu ta muốn người thứ i thắng → ta cần tìm cách dàn xếp tỷ số giữa các trận chưa đấu sao cho khi đã đấu hết không có có điểm lớn hơn mx[A]

Dựng mô hình đồ thị với các đỉnh là người chơi, cạnh là kết quả trận đấu

Tạm thời bỏ qua tỷ số hòa thì ta cho 1 cạnh (u, v) có 3 trường hợp

• u→v: v thắng u
• u←v: u thắng v
• u—v: chưa đấu

lúc này nếu ta thêm trọng số vào cạnh (u, v, w). Thì có thể hiểu là ta đổ 1 lượng điểm bé hơn hoặc bằng w từ v vào u

từ nhận xét trên ta có thể tạo được mô hình luồng → với cạnh chưa đấu thì ta cần định chiều lại cạnh đó sao cho khi kết thúc thì tỷ số là thỏa đề

Định chiều bằng luồng

Khi định chiều thì ta sẽ đổ luồng vào cạnh, hướng của luồng đi qua cạnh sẽ là chiều của cạnh.

Giờ ta xử lý trường hợp hòa.

KEY:

• ta sẽ đổ luồng vào giữa cạnh → nếu hòa thì là điểm chia đều cho u, v → luồng đi qua 2 bên
• từ đó với mỗi cạnh u→v ta tạo 1 đỉnh ảo và đổ luồng vào đỉnh này sau đó chạy thuật toán luồng cực đại

Cài đặt

Dựng đồ thị G(V, E)

ta sẽ coi trận thắng là 2 điểm, thua 0, hòa 1 mỗi bên

ta có X trận chưa đấu thì cùng với n người ban đầu (n đỉnh ban đầu) ta sẽ thêm X + 2 đỉnh ảo nữa. Mỗi cạnh là 1 đỉnh, và 2 đỉnh s, t

khi thêm đỉnh giữa y cạnh u, v → ta sẽ thêm 2 cạnh có hướng (y, u, 2) và (y, v, 2) vào đồ thị.

Sau khi thêm đủ cạnh:

• #1 ta sẽ nối từ s 1 cạnh có hướng đi vào mọi đỉnh m giữa cạnh, ta thêm cạnh có hướng (s, m, 2)
• #2 với từng người thi đấu c, khác người ta đang muốn thắng, ta sẽ thêm 1 cạnh có hướng (c, t, mx[i] - p[c]) vào đồ thị (có nghĩa là người này chỉ có thể nhận thêm tối đa mx[i] - p[c] điểm

Vì với 1 đỉnh, luồng vào = luồng đi nên #2 sẽ cho ta đáp án tối ưu

và vì luồng chạy trên đơn vị 1 nên ở vị trí hòa → luồng sẽ chắc chắn chia đôi

//Code
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "chess"
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i ++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 30 + 5;

ll n, p[N], mx[N], tmp[N];
char a[N][N];

struct flow {
    int sz;
    vector <vector <ll>> cap, d;

    flow(int n) {
        sz = n;
        cap.resize(n + 2, vector <ll> (n + 2, 0));
        d.resize(n + 2);
    }

    void addEdge(int u, int v, int w) {
        cap[u][v] = w;
        d[u].push_back(v);
        d[v].push_back(u);

        // cout << u << ' ' << v << ' ' << w << '\n';
    }

    int bfs(int s, int t, vector <int> &par) {
        fill(par.begin(), par.end(), -1);
        par[s] = -2;

        queue <pii> q;
        q.push({s, INF});

        while (q.size()) {
            int cur = q.front().st;
            ll flow = q.front().nd;
            q.pop();

            // cout << cur << ' ' << flow << '\n';

            for (int nxt: d[cur]) {
                    // cout << "i was here: " << par[nxt] << ' ' << cap[cur][nxt] << '\n';
                if (par[nxt] == -1 && cap[cur][nxt] ) {
                    par[nxt] = cur;
                    int new_flow = min(flow, cap[cur][nxt]);
                    if (nxt == t) return new_flow;

                    q.push({nxt, new_flow});
                }
            }
        }

        return 0;
    }

    int maxFlow(int s, int t) {
        int flow = 0;
        vector <int> par(sz + 2);

        int new_flow = 0;
        while (new_flow = bfs(s, t, par)) {
            flow += new_flow;

            int cur = t;
            while (cur != s) {
                int pre = par[cur];
                cap[pre][cur] -= new_flow;
                cap[cur][pre] += new_flow;
                cur = pre;
            }
        }

        return flow;
    }
};

bool check(ll c) {
    rep(i, 1, n) tmp[i] = p[i];
    rep(i, 1, n) if (a[c][i] == '.') tmp[c] += 2;

    rep(i, 1, n) if (p[i] > tmp[c]) return false;

    int NumEdge = 0, NumNode = n + 2;

    rep(i, 1, n) if (i != c) {
        rep(j, i + 1, n) if (a[i][j] == '.')
            NumNode ++;
    }

    int source = 0, sink, flowGo = 0;
    flow Ford_Fulkerson(NumNode);

    NumEdge = n;

    rep(i, 1, n) if (i != c) {
        rep(j, i + 1, n) if (j != c && a[i][j] == '.') {
            NumEdge ++;
            Ford_Fulkerson.addEdge(NumEdge, i, 2);
            Ford_Fulkerson.addEdge(NumEdge, j, 2);
            Ford_Fulkerson.addEdge(source, NumEdge, 2);
            flowGo += 2;
        }
    }

    sink = NumEdge + 1;
    rep(i, 1, n) if (i != c)
        Ford_Fulkerson.addEdge(i, sink, max(0ll, tmp[c] - tmp[i]));

    ll maxFlow = Ford_Fulkerson.maxFlow(source, sink);
    // cout << "Begin: " << source << ' ' << sink << ' ' << '\n';
    // cout << "Flow go: " << flowGo << '\n';
    // cout << "Flow found: " << maxFlow << '\n';
    return maxFlow == flowGo;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n;
    rep(i, 1, n) rep(j, 1, n) {
        cin >> a[i][j];
        if (a[i][j] == '1') p[i] += 2;
        if (a[i][j] == 'd') p[i] += 1;
    }

    // rep(i, 1, n) cout << p[i] << ' '; cout << '\n';

    vector <int> ans;

    rep(i, 1, n) if (check(i))
        ans.push_back(i);

    for (int i: ans) cout << i << ' ';

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮
**/