首页 > 代码库 > 被sjy带刷题#1
被sjy带刷题#1
笔记
【问题描述】
给定一个长度为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-1using 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(1);queue<int> que;int main(){ ios::sync_with_stdio(false); cin >> n >> m; for (int i=1;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=1;i<=n;i++) dis[i] = 0x7fffff; que.push(1);d[1] = 1;dis[1] = 0; do{ int h = que.front();d[h] = 0; que.pop(); for (int i=1;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]] = 1; } } } }while(!que.empty()); que = queue<int>(); memset(d, 0, sizeof(d)); que.push(1),d[1] = 1,sum[1] = 1; do{ int h = que.front();d[h] = 0; que.pop(); for (int i=1;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]] = 1 : sum[s[h][i]]++; if (!d[s[h][i]]) { que.push(s[h][i]),d[s[h][i]] = 1; } } } }while(!que.empty()); for (int i=1;i<=n;i++) ans=(ans*sum[i])%m; cout << ans << endl; return 0;}
被sjy带刷题#1