L2-044 大众情人分数 25分

水深无声 2023-09-26 20:54 135阅读 0赞

![0b55cf3fbdefa434254cb57500d480c8.jpeg][]

人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。

一个人的异性缘不是由最喜欢他/她的那个异性决定的，**而是由对他/她最无感的那个异性决定的。我们记一个人 i 在一个异性 j 眼中的距离感为 Dij；将 i 的“异性缘”定义为 1/maxj∈S(i)\{Dij\}，其中 S(i) 是相对于 i 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。**

本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。

#### 输入格式： ####

输入在第一行中给出一个正整数 N（≤500），为总人数。于是我们默认所有人从 1 到 N 编号。

随后 N 行，第 i 行描述了编号为 i 的人与其他人的关系，格式为：

性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K

其中 `性别` 是这个人的性别，`F` 表示女性，`M` 表示男性；`K`（<N 的非负整数）为这个人直接认识的朋友数；随后给出的是这 `K` 个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过 106 的正整数。

题目保证给出的关系中一定两种性别的人都有，不会出现重复给出的关系，并且每个人的朋友中都不包含自己。

#### 输出格式： ####

第一行给出自身为女性的“大众情人”的编号，第二行给出自身为男性的“大众情人”的编号。如果存在并列，则按编号递增的顺序输出所有。数字间以一个空格分隔，行首尾不得有多余空格。

#### 输入样例： ####

6
    F 1 4:1
    F 2 1:3 4:10
    F 2 4:2 2:2
    M 2 5:1 3:2
    M 2 2:2 6:2
    M 2 3:1 2:5

#### 输出样例： ####

2 3
    4

> 代码长度限制
> 
> 16 KB
> 
> Java (javac)
> 
> 时间限制
> 
> 1200 ms
> 
> 内存限制
> 
> 128 MB
> 
> 其他编译器
> 
> 时间限制
> 
> 400 ms
> 
> 内存限制
> 
> 64 MB

思路：floyd()算法没啥说的，暂时没别的办法了。

坑点：知道是“**对他/她最无感的那个异性决定的**”就行了，后面那一串公式就是用来**坑**你的，是不是感觉表述不清楚，还在吐槽题目……………………，

**对他/她**最无感的异性，那就是**==**所有异性眼中，**距离他/她最远**的那个值决定的，不用管那个值是多少，**反正距离最远就对了**

若g\[i\]\[j\]表示 i 对 j 的距离， 那么需要找的应该是所有异性 g\[j\]\[i\]的值中最大的那一个作为 i 的异性缘指标，

然后假设有 s 个女性 / 男性 ,还得从 s 个指标中找最小的那一个是属于谁的，谁才是大众情人

![d6673dc889234f14bd1c87b853f860eb.png][]

#include<bits/stdc++.h>
    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int N=505;
    
    vector<int>F,M;
    queue<int>que;
    int g[N][N];
    
    
    int solve(int n){   
    	//floyd算法 
    	for(int k=1;k<=n;k++)
    	for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)
    	g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    
    //查看数据	
    //	for(int i=1;i<=n;i++){
    //		cout<<"   "<<FM[i]<<i<<"  ";
    //	for(int j=1;j<=n;j++) printf("%5d  ",g[i][j]);
    //	cout<<endl;	
    //	}
    
    	//女生大众情人 
    	int min_D=INF;
    	for(int i=0;i<F.size();i++){
    		int Dij=0;
    		for(int j=0; j<M.size(); j++){//寻找所有男性眼中她是最远的那个值 
    			Dij=max(Dij,g[M[j]][F[i]]);				
    //			printf("   D%d%d=%-3d",M[j],F[i],g[M[j]][F[i]]);
    		}
    //		cout<<"--> 女"<<F[i]<<" : "<<Dij<<endl;
    		if(Dij<min_D){
    			min_D=Dij;
    			while (!que.empty()) que.pop();	
    			que.push(F[i]); 
    		} 									
    		else if( Dij==min_D)  que.push(F[i]);	
    	}	
    	
    	if(!que.empty()){  cout<<que.front();	que.pop(); }			
    	while(!que.empty()) { cout<<" "<<que.front();	que.pop(); }
    	cout<<endl;
    		
    	//男生大众情人 
    	int max_D=INF;
    	for(int i=0;i<M.size();i++){
    		int Dij=0;
    		for(int j=0; j<F.size(); j++){//寻找所有男性眼中她是最远的那个值 
    			Dij=max(Dij,g[F[j]][M[i]]);				
    //			printf("   D%d%d=%-3d",F[i],M[j],g[F[j]][M[i]]);
    		}
    //		cout<<"  男"<<M[i]<<" : "<<Dij<<endl;
    		
    		if(Dij<max_D){
    			max_D=Dij;
    			while (!que.empty()) que.pop();	
    			que.push(M[i]); 
    		} 									
    		else if( Dij==max_D)  que.push(M[i]);	
    	}	
    	
    	if(!que.empty()){  cout<<que.front();	que.pop(); }		
    	while(!que.empty()) { cout<<" "<<que.front();	que.pop(); }
    	cout<<endl;	
    }
    
    int main(){
    	//cin.tie(0)->sync_with_stdio(false); cout.tie(0);
    	memset(g,INF,sizeof g);
    	int n,k,j,dis;	
    	char fm; 
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		g[i][i]=0;	
    		cin>>fm>>k;
    		if(fm=='F')	F.push_back(i);
    		else 	M.push_back(i); 
    		while(k--) { 
    			scanf("%d:%d",&j,&dis); 
    			g[i][j]=dis; 
    		}		
    	}
    	solve(n);
    	return 0;
    }

[0b55cf3fbdefa434254cb57500d480c8.jpeg]: https://img-blog.csdnimg.cn/img_convert/0b55cf3fbdefa434254cb57500d480c8.jpeg
[d6673dc889234f14bd1c87b853f860eb.png]: https://img-blog.csdnimg.cn/d6673dc889234f14bd1c87b853f860eb.png