1024 Currency Exchange Centers (35分)

解题思路：

直接说吧，现在网上的版本应该是没有一个是真正对的，都无法处理以下情况：

很明显答案应该是只需要一个center即可，但是由于现存版本在所有center都未出现时选center的随机性，一开始会选到ACC的情况，直接导致答案错误：

输入：
3 3
0 1 ABC 1
0 2 ACC 1
1 2 ACC 1
输出：
2 2
0 1 ABC 1
0 2 ACC 1
期望：
1 2
1 2 ACC 1
0 2 ABC 1

但是将错就错，给出能AC思路：
很明显这题是MST，加了一个条件是要求中心个数最少，那么我们按照贪心思想，使用优先队列，每次优先按照fee作为第一关键字（参考克鲁斯卡尔最小生成树），该边的中心是否出现过作为第二关键字排序，即可得到“最优解”。
（一开始想过这个思路，被自己秒否决了，然后各种尝试都答案错了，最后也没能得到正解，很烦躁，浪费

代码：

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define G 6.67430*1e-11
#define
rd read()
#define pi 3.1415926535
#define pdd pair<double,double>
using namespace std;
const ll mod = 1e9 + 7;
const int MAXN = 30000005;
const int MAX2 = 300005;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
ll fpow(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
int fa[100005];
int find(int r) { return fa[r] == r ? r : fa[r] = find(fa[r]); }
void join(int x, int y)
{
int fx = find(x), fy = find(y);
fa[fx] = fy;
}
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
map<string, int> nameflag;
struct ss
{
int s, e, fee;
string name;
bool operator < (const ss& b)const
{
return this->fee > b.fee || (this->fee == b.fee && nameflag[this->name] < nameflag[b.name]);
}
}edge[10005];
vector<ss> ans;//存放MST的边
int sum = 0;//统计和
int namecount = 0;
priority_queue<ss> p;//<<权值*-1，编号>>
bool cmp(ss a, ss b) { return a.fee < b.fee; }
bool cmp_print(ss a, ss b) { return a.name < b.name || (a.name == b.name && a.fee < b.fee); }
signed main()
{
int n = rd, m = rd;
for (int i = 0; i < n; i++)fa[i] = i;
for (int i = 0; i < m; i++)
{
edge[i].s = rd;
edge[i].e = rd;
cin >> edge[i].name;
edge[i].fee = rd;
p.push(edge[i]);
}
while (p.size())
{
auto now = p.top();
if (find(now.s) != find(now.e))
{
if(!nameflag[now.name])namecount++;
nameflag[now.name] = 1;//更新已存在的中心
join(now.s, now.e);
ans.push_back(now);
sum += now.fee;
}
p.pop();
}
cout << namecount << ' ' << sum << endl;
sort(ans.begin(), ans.end(), cmp_print);
for (auto p : ans)
{
printf("%d %d %s %dn", p.s, p.e, p.name.c_str(), p.fee);
}
return 0;
}

最后

以上就是奋斗发箍为你收集整理的PAT顶级（MST+优先队列——可HACK）——1024 Currency Exchange Centers (35分)1024 Currency Exchange Centers (35分)的全部内容，希望文章能够帮你解决PAT顶级（MST+优先队列——可HACK）——1024 Currency Exchange Centers (35分)1024 Currency Exchange Centers (35分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。