笔记
【问题描述】
给定一个长度为m的序列a，下标编号为1~m。序列的每个元素都是1~n的
整数。定义序列的代价为你现在可以选择两个数x和y，并将序列a中所有的x改成y。x可以与y相等。
请求出序列最小可能的代价。
【输入格式】
输入第一行包含两个整数n和m。第二行包含m个空格分隔的整数，代表序
列a。
【输出格式】
输出一行，包含一个整数，代表序列最小的代价。
【样例输入 1】
4 6
1 2 3 4 3 2
【样例输出 1】
3
【样例输入 2】
10 5
9 4 3 8 8
【样例输出 1】
6
【样例解释】
样例 1 中，最优策略为将 4 改成 3。样例 2 中，最优策略为将 9 改成 4。
【数据规模和约定】对于30%的数据，n,m<=100.
对于60%的数据，n,m ≤ 2000。
对于100%的数据，1 ≤ n,m≤ 100,000。
城堡
【问题描述】
给定一张N个点M条边的无向连通图，每条边有边权。我们需要从M条边中
选出N − 1条， 构成一棵树。 记原图中从 1 号点到每个节点的最短路径长度为Di ，
树中从 1 号点到每个节点的最短路径长度为? ? ，构出的树应当满足对于任意节点
i，都有Di = Si 。
请你求出选出N − 1条边的方案数。
【输入格式】
输入的第一行包含两个整数N和M。
接下来M行，每行包含三个整数u、v和w，描述一条连接节点u和v且边权为
w的边。
【输出格式】
输出一行，包含一个整数，代表方案数对2^31 − 1取模得到的结果。
【样例输入】
3 3
1 2 2
1 3 1
2 3 1
【样例输出】
2
【数据规模和约定】
对于20%的数据，2<=N<=5，M<=10.
对于50%的数据，满足条件的方案数不超过 10000。
对于100%的数据，2≤ N ≤ 1000，N-1 ≤ M ≤ N(N-1)/2，1<=w<=100.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 1000
#define maxm 500000
#define mod 1<<31-1
using namespace std;
typedef long long LL;
int m,n;
int w[maxn][maxn], s[maxn][maxn], num[maxn], d[maxn];
LL dis[maxn], sum[maxn], ans();
queue<int> que;
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i=;i<=m;i++) {
int u,v,value;cin>>u>>v>>value;
w[u][v] = w[v][u] = value;
s[u][++num[u]] = v;
s[v][++num[v]] = u;
}
for (int i=;i<=n;i++) dis[i] = 0x7fffff;
que.push();d[] = ;dis[] = ;
do{
int h = que.front();d[h] = ;
que.pop();
for (int i=;i<=num[h];i++){
if (dis[s[h][i]] > dis[h] + w[h][s[h][i]]){
dis[s[h][i]] = dis[h] + w[h][s[h][i]];
if (!d[s[h][i]]){
que.push(s[h][i]),d[s[h][i]] = ;
}
}
}
}while(!que.empty());
que = queue<int>();
memset(d, , sizeof(d));
que.push(),d[] = ,sum[] = ;
do{
int h = que.front();d[h] = ;
que.pop();
for (int i=;i<=num[h];i++){
if (dis[s[h][i]] == dis[h]+w[h][s[h][i]]){
sum[s[h][i]] == mod ? sum[s[h][i]] = : sum[s[h][i]]++;
if (!d[s[h][i]]) {
que.push(s[h][i]),d[s[h][i]] = ;
}
}
}
}while(!que.empty());
for (int i=;i<=n;i++) ans=(ans*sum[i])%m;
cout << ans << endl;
return ;
}
castle.cpp