tyvj3412 流言的传播 【最小生成树】
描述
流言的传播（rumor.pas\c\cpp）
【题目描述】
昨天下午，Matrix67陪MM出去逛街，走累了后去咖啡店歇了歇脚；再后来MM陪Matrix67去了一趟书店，之后两人去电影院看了一场电影。从电影院出来后已经很晚了，考虑到MM的安全问题，Matrix67先送MM回到宿舍，然后自己才回去。第二天Matrix67起床后发现问题严重了：昨天和MM出去玩本来什么都没发生，但现在一些不堪入耳的流言正疯狂传播，很多细节都说得有鼻子有眼的。在澄清事实并抓出元凶的同时，Matrix67希望切断一些流言传播的路径，尽可能减缓流言传播的速度。
除去Matrix67和他的MM，学校里还有N个人。这N个人形成了M对双向的朋友关系，这些朋友关系连通了所有N个人。不同的朋友间传递消息的速度各不相同。如果A和B是第i对朋友，那么当其中一个人听到流言后，他会在Ti的时间内传给另一个人。现在，Matrix67只知道流言并没有传遍整个学校，但他不知道哪些人已经听说了这个流言。他希望切断尽可能少的朋友关系，使得无论是哪些人已经获知了流言，流言都无法以原来的速度传给一个新的人（即新的得知此流言的人的出现将变得更晚）。换句话说，Matrix67希望找到一个最小的边集E，使得对任意一个不等于全集的点集S，恰好只有一个顶点在S里的边中权值最小的那一条在边集E中。
输入格式
输入文件rumor.in第一行输入两个用空格隔开的正整数N和M，分别表示学校的人数和朋友关系数。
以下M行每行有三个用空格隔开的正整数，其中第i行的三个正整数为Ai, Bi, Ti，表示Ai和Bi是第i对朋友，它们之间传递消息需要Ti的时间。输入数据保证0
输出格式
你需要输出你所得到的最小值和具体的方案。
输出文件rumor.out的第一行是一个正整数，代表你的最优方案中需要切断的朋友关系数。
以下若干行每行一个正整数，表示你的方案里需要切断的朋友关系在输入数据中的编号（即你需要切断的是输入数据中给的第几条边）。这些数必须按照增序排列输出。
如果有多种最优方案，你只需要输出其中一种即可。我们的评测系统会自动判断你的输出数据的正确性。
测试样例1
输入
4 4
1 2 2
4 3 4
2 3 3
1 3 1
输出
3
1
2
4
备注
【样例说明】
（１）
ｏ
／ ＼
１ ／ ＼ ２
／ ＼
（４） ｏ－－－－－－－ｏ－－－－－－－ｏ （２）
４ （３） ３
首先，(3)---(4)这条边必须去掉，否则若只有4号同学得知流言，流言将以相同的速度传给下一个人。对于其它三条边，只需要去掉权值较小的两条即可，这样不论获知流言的是哪个（些）人，所有可以继续向外传播流言的边中最小的那一条一定已经被去掉了。可以证明，去掉三条边已经是最优的答案了。
【数据规模】
对于30%的数据，N
对于50%的数据，N
对于100%的数据，N
【题解】
观察发现，就是最小生成树啦~
# include <stdio.h>
# include <algorithm>
using namespace std;
int n,m;
struct d {
int u,v,w,id;
}e[1000010];
int cnt=0,a[1000010];
int fa[1000010];
int getf(int x) {
int r=x;while(fa[r]!=r)r=fa[r];
int i=x,j;
while(i!=r) j=fa[i],fa[i]=r,i=j;
return r;
}
inline int cmp(d a,d b) {
return a.w<b.w;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),e[i].id=i;
for(int i=1;i<=n;++i)fa[i]=i;sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;++i) {
int fu=getf(e[i].u),fv=getf(e[i].v);
if(fu==fv)continue;
fa[fu]=fv;a[++cnt]=e[i].id;
if(cnt==n-1)break;
}sort(a+1,a+cnt+1);
printf("%d\n",n-1);
for(int i=1;i<=cnt;++i)printf("%d\n",a[i]);
}
评论 (0)
