7-14 社交集群（30）
题意
给定 (n) 个人的爱好，求这 (n) 个人一共组成了多少个圈子，每个圈子的大小。
题解
使用并查集维护即可。
代码
#include <bits/stdc++.h>
using namespace std;
int p[1005], n, a[1005];
int Find(int x){
if(p[x] != x) p[x] = Find(p[x]);
return p[x];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) p[i] = i;
for(int i = 1; i <= n; ++ i) {
int k, h;
scanf("%d:", &k);
while(k --) {
cin >> h;
if(a[h]) p[Find(i)] = Find(a[h]);
else a[h] = i;
}
}
map<int, int> cnt;
for(int i = 1; i <= n; ++ i)
cnt[Find(i)] ++;
vector<int> v;
for(auto x : cnt)
v.push_back(x.second);
sort(v.begin(), v.end(), greater<int>());
cout << v.size() << '
' << v[0];
for(int i = 1; i < v.size(); ++ i)
cout << ' ' << v[i];
cout << endl;
return 0;
}
垃圾箱分布（30）
对每一个垃圾桶选择点都进行 Dijkstra，在 dis 数组的最大值不大于 dis 的情况下，选择 dis 的数组的最小值最大的，如果最小值一样就选择和最小的。
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,k,m,ds;
int e[1205][1205];
bool v[1205];
int d[1205];
int kk=1;
struct node
{
int bh;
double p;
int h;
int zd;
}a[15];
bool cmp(node x,node y)
{
if(x.zd==y.zd)
{
if(x.p==y.p)
return x.bh<y.bh;
else return x.p<y.p;
}
else return x.zd>y.zd;//最短距离要最长
}
void dijstra(int s)
{
int i;
memset(v,0,sizeof(v));
v[s]=1;
int zd=inf;
for(i=1;i<=n+m;i++)
{
d[i]=e[s][i];
if(!v[i]&&i<=n&&d[i]<zd)//条件要写全
zd=d[i];
}
while(1)
{
int k=-1;
int mm=inf;
for(i=1;i<=n+m;i++)
{
if(!v[i]&&d[i]<mm)
{
k=i;
mm=d[i];
}
}
if(k==-1) break;
v[k]=1;
for(i=1;i<=n+m;i++)
{
if(d[i]>d[k]+e[k][i])
{
d[i]=d[k]+e[k][i];
if(!v[i]&&i<=n&&d[i]<zd)
zd=d[i];//把最短的距离找出来
}
}
}
int ss=0;
for(i=1;i<=n;i++)
{
if(d[i]>ds) break;//最短路径超出范围的不要
else ss+=d[i];
}
if(i==n+1)
{
a[kk].bh =s-n;
a[kk].h=ss;
a[kk].zd=zd;
a[kk++].p=ss*1.0/n;
}
}
int main()
{
cin>>n>>m>>k>>ds;
int i,j;
for(i=1;i<=n+m;i++)
for(j=1;j<=n+m;j++)
{
if(i==j) e[i][j]=0;
else e[i][j]=inf;
}
for(i=1;i<=k;i++)
{
string a,b;//G的处理
int z;
cin>>a>>b>>z;
int x=0,y=0;
if(a[0]!='G')
{
int l=a.length ();
for(int i=0;i<l;i++)
{
x=x*10+a[i]-'0';
}
}
else
{
int l=a.length ();
for(int i=1;i<l;i++)
{
x=x*10+a[i]-'0';
}
x+=n;
}
if(b[0]!='G')
{
int l=b.length ();
for(int i=0;i<l;i++)
{
y=y*10+b[i]-'0';
}
}
else
{
int l=b.length ();
for(int i=1;i<l;i++)
{
y=y*10+b[i]-'0';
}
y+=n;
}
if(e[x][y]>z)
{
e[x][y]=z;
e[y][x]=z;
}
}
for(int i=n+1;i<=m+n;i++)//遍历每一个垃圾箱
{
dijstra(i);
}
if(k==1) cout<<"No Solution";
else
{
sort(a+1,a+kk,cmp);//排个序，是kk
if(a[1].bh==0) cout<<"No Solution";
else
{
cout<<"G"<<a[1].bh<<endl;
printf("%.1lf",a[1].zd*1.0);cout<<" ";
printf("%.1lf",a[1].p);
}
}
return 0;
}
地铁一日游 (30)
这道题的结点数较少，所以我们可以用Floyed求出最短路径。
然后我们对于每一个站点i，都求出在花费相同时可以到达的最远的站点，把这些站点都作为i的候选站点。
接着对于每一次查询，我们用一次dfs把从开始结点出发可以到达的所有结点都打上标记，接着我们只要输出标记等于本次查询序号的结点即可。
注意坐地铁是可以来回往返的，所以要用dfs。
#include<stdio.h>
#include<iostream>
#include<map>
#include<vector>
#define MAX 205
#define INF 0x3f3f3f3f
using namespace std;
struct station{
int visit,ends;
station(){
visit=ends=0;
}
vector<int> res;//所有可到达的站
}sta[MAX];
int mp[MAX][MAX];
int n,m,k;
void floyed(){//Floyed求最短路径
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j&&mp[i][j]>mp[i][k]+mp[k][j]){
mp[i][j]=mp[i][k]+mp[k][j];
}
}
}
}
}
void dfs(int i,int vis){
for(int j=0;j<sta[i].res.size();j++){
int t=sta[i].res[j];
if(sta[t].visit!=vis){
sta[t].visit=vis;
dfs(t,vis);
}
}
}
int main(){
for(int i=0;i<MAX;i++){
for(int j=0;j<MAX;j++){
mp[i][j]=INF;
}
}
scanf("%d%d%d",&n,&m,&k);
int a,b,len;
for(int i=0;i<m;i++){
scanf("%d",&a);
sta[a].ends=1;
do{
scanf("%d%d",&len,&b);
if(len<mp[a][b]) mp[a][b]=mp[b][a]=len;
a=b;
}while(getchar()!='
');
sta[a].ends=1;
}
floyed();//求出最短路径
for(int i=1;i<=n;i++){//对于每个站而言，寻找每个费用的最远距离,并将结果存入res中
map<int,int> m1;
for(int j=1;j<=n;j++){
if(mp[i][j]!=INF&&mp[i][j]>m1[mp[i][j]/k+2]){
m1[mp[i][j]/k+2]=mp[i][j];
}
}
for(int j=1;j<=n;j++){
if(mp[i][j]==m1[mp[i][j]/k+2]||(i!=j&&mp[i][j]!=INF&&sta[j].ends==1)){
sta[i].res.push_back(j);
}
}
}
int q,start;
scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%d",&start);
sta[start].visit=i;//打上标记i
dfs(start,i);//将所有可能的站都打上标记i
int flag=0;
for(int j=1;j<=n;j++){
if(sta[j].visit==i){
printf("%s%d",flag==0?"":" ",j);
flag=1;
}
}
printf("
");
}
return 0;
}