[编程题]社团主席选举

[编程题]社团主席选举

时间限制：1秒

空间限制：262144K

随着又一届学生的毕业，社团主席换届选举即将进行。

一共有n个投票者和m个候选人，小易知道每一个投票者的投票对象。但是，如果小易给某个投票者一些糖果，那么这个投票者就会改变他的意向，小易让他投给谁，他就会投给谁。

由于小易特别看好这些候选人中的某一个大神，这个人的编号是1，所以小易希望能尽自己的微薄之力让他当选主席，但是小易的糖果数量有限，所以请你帮他计算，最少需要花多少糖果让1号候选人当选。某个候选人可以当选的条件是他获得的票数比其他任何候选者都多。

输入描述:

第一行两个整数n和m，表示投票者的个数和候选人的个数。
接下来n行，每一行两个整数x和y，x表示这个投票者的投票对象，y表示需要花多少个糖果让这个人改变意向。
满足1 <= n, m <= 3000，1 <= x <= m，1 <= y <= 109。

输出描述:

一个整数，糖果的最小花费。

输入例子1:

1 2
1 20

输出例子1:

0

输入例子2:

5 5
2 5
3 5
4 5
5 6
5 1

输出例子2:

6

#include <bits/stdc++.h>
using namespace std;
#define N 3001
int n, m;
int x[N], y[N];
bool vis[N];
long ans = LONG_MAX;
unordered_map<int, int> cnt;int candidate_max()
{//找到最多支持者的候选人int candidate = -1, tmp = 0;for(int i = m; i > 0; --i) {if(cnt[i] > tmp) {tmp = cnt[i];candidate = i;}}return candidate;
}pair<int, int> idx_min(int candidate)
{//找到两种选择的投票人的下标int c_min = INT_MAX, t_min = INT_MAX, c_idx, t_idx;for(int i = 0; i < n; ++i) {if(vis[i]) continue;if(t_min > y[i]) {t_min = y[i];t_idx = i;}if(x[i] == candidate) {if(c_min > y[i]) {c_min = y[i];c_idx = i;}}}return make_pair(t_idx, c_idx);
}void dfs(long cost)
{if(cost >= ans) return;int candidate = candidate_max();if(candidate == 1) {if(cost < ans) ans = cost;return;}pair<int, int> idx = idx_min(candidate);// 收买花费最少的vis[idx.first] = true;cnt[1]++;cnt[x[idx.first]]--;dfs(cost + y[idx.first]);vis[idx.first] = false;cnt[1]--;cnt[x[idx.first]]++;if(idx.first == idx.second) return;// 收买最多得票的支持者中花费最少的vis[idx.second] = true;cnt[1]++;cnt[x[idx.second]]--;dfs(cost + y[idx.second]);vis[idx.second] = false;cnt[1]--;cnt[x[idx.second]]++;
}int main(void)
{memset(vis, 0, sizeof(0));cin>>n>>m;for (int i = 0; i < n; i++) {cin>>x[i]>>y[i];cnt[x[i]]++;}dfs(0);cout<<ans;return 0;
}