UVa 11748 – Rigging Elections [求可达矩阵]

Link

传送门

Problem

Elections in your country are performed in a one-on-one elimination style. Each week, two people are chosen from a pool of candidates and the country votes on which one they prefer. The loser is eliminated and the winner is returned to the pool of candidates. This process continues until only one candidate remains.

To make a bad voting system even worse, a single person is charged with the responsibility of choosing the two candidates each week. This person happens to be you! Since you are a very selfish person, you plan on rigging the election so your preferred candidate wins. You have access to polling data from which you can determine who would win in every possible head-to-head matchup. Assuming the data accurately represents what the real outcome would be, is it possible to schedule the candidates so your candidate wins?

Mean

有n个候选人m个投票人,每个投票人都有对n个人的支持次序。你可以安排n个人的选举活动,每次两个人竞争,支持者少的退出。现在问你有没有一种竞争顺序,使得c获胜。

Analysis

首先预处理出任意两个人竞争谁可以获胜,a打败b相当于图论中一条边a->b,那么我们用类似于Floyd算法求出可达矩阵,看看c是否可以到达其他所有点。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;
int N, M, C, cnt[maxn][maxn], t[maxn], dp[maxn][maxn];

int main() {
    while(cin >> N >> M >> C, N||M||C) {
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= M; ++i) {
            for(int j = 1; j <= N; ++j)
                cin >> t[j];
            for(int j = 1; j <= N; ++j)
                for(int k = j + 1; k <= N; ++k)
                    ++cnt[t[j]][t[k]];
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= N; ++i) {
            for(int j = i + 1; j <= N; ++j) {
                if(cnt[i][j] > cnt[j][i]) dp[i][j] = 1;
                else dp[j][i] = 1;
            }
        }
        for(int k = 1; k <= N; ++k)
            for(int i = 1; i <= N; ++i)
                for(int j = 1; j <= N; ++j)
                    dp[i][j] = dp[i][j] || (dp[i][k] && dp[k][j]);
        bool ok = true;
        for(int i = 1; i <= N; ++i)
            if(i != C && !dp[C][i])
                ok = false;
        cout << (ok ? "yes" : "no") << endl;
    }
    return 0;
}

2 条评论

欢迎留言