首页 > 代码库 > 【图论】蒜厂年会
【图论】蒜厂年会
蒜厂要开年会了，所有的员工都要参加。
每两个员工之间都有一个亲密度。在同一个项目工作过的员工之间的亲密度为 11。如果 A 和 B、B 和 C 均在同一个项目中工作过，而 A 和 C 没有，那么 A 和 C 之间的亲密度为 1+1=21+1=2。
同理，如果 A 和 B 之间的亲密度为 xx，B 和 C 之间的亲密度为 yy，则 A 和 C 之间的一种 可能亲密度 为 x+yx+y。两个人之间的 亲密度 为所有的 可能亲密度 之中的 最小值。
因为蒜厂里员工之间非常有爱，所以 保证每两个员工之间都可以算出一个亲密度。
现在有一个名单，一直蒜厂在这一年一共进行过 MM 个项目，NN 名员工都想知道自己与其他所有员工的亲密度的平均值，现在你需要找出所有员工中，与其他所有员工 亲密度平均值 最小的员工，即和其他所有员工最亲密的一名员工，来担任这次年会的主持人。
输入格式
一行两个整数 NN 和 MM，(1\leq M\leq 10000,2\leq N\leq 300)(1≤M≤10000,2≤N≤300)。
接下来 MM 行，表示 MM 个项目名单,每行第一个整数表示参加这一个项目的员工人数，后面是这些员工的编号，所有员工的编号从 11 开始计数。
输出格式
一行一个整数，为最小的亲密度平均值乘 100100 以后向下取整。
样例输入
4 23 1 2 32 3 4
样例输出
100
这个题差不多算是一个裸的Floyd多源最短路问题，但是有些细节问题需要特别注意一下。
首先是在读入的时候，只要是共同工作过他们的权值都是1.
其次是小技巧，最后算那个加和值的时候，先不要*100/n啊啥的，放到最后算。可以略微的优化
#include <iostream>using namespace std;int f,g,h=1,q,n,m,a[301][301],total,da=10000,s[1001];int inf=999999;int main(){ cin>>n>>m; //n个员工 m个项目 for(int j=1;j<=n;j++){ //初始化边 for(int k=1;k<=n;k++){ if(j == k) a[j][k]=0; else a[j][k]=inf; } } for(int i=1;i<=m;i++){ //把每个项目 工作的人 权重赋1 cin>>q; for(int j=0;j<q;++j) cin>>s[j]; for(int j=0;j<q;++j) for(int b=1;b<q;++b) a[s[j]][s[b]]=1; } for(int k=1;k<=n;k++) //Floyd核心语句 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j] > a[i][k]+a[k][j] && a[i][k]<inf && a[k][j]<inf) a[i][j]=a[i][k]+a[k][j]; for(int i=1;i<=n;i++){ //把每个点的所有边先进行加和 求出最小的那个 for(int j=1;j<=n;j++){ total = a[i][j] + total; } if(total < da ) da = total ; total = 0; } da = da * 100 / n; //最小的那个 先*100 再除去n cout<<da<<endl;//输出 return 0;}//差不多就是一个裸的Floyd题 不过需要注意小细节问题
【图论】蒜厂年会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。