目录

1.Head of a Gang

2.邻接矩阵版bfs

3.邻接表

4.带层号

5.Forwards on Weibo

---

1.Head of a Gang

#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

const int maxn=2005;
int g[maxn][maxn]={0},weight[maxn]={0};
map<string,int> stringtoint;
map<string,int> gang;
map<int,string> inttostring;
bool vis[maxn]={false};
int n,k;

void dfs(int nowvisit,int &head,int &membernum,int &totalweight){
	membernum++;
	vis[nowvisit]=true;
	if(weight[nowvisit]>weight[head]){
		head=nowvisit;
	}
	for(int i=0;i<n;i++){
		if(g[i][nowvisit]>0){
			totalweight+=g[i][nowvisit];
			g[i][nowvisit]=g[nowvisit][i]=0;
			if(vis[i]==false){
				dfs(i,head,membernum,totalweight);
			}
		}
	}
}

void dfstrave(){
	for(int i=0;i<n;i++){
		if(vis[i]==false){
			int head=i,membernum=0,totalweight=0;
			dfs(i,head,membernum,totalweight);
			if(membernum>2&&totalweight>k){
				gang[inttostring[head]]=membernum;
			}
		}
	}
}

int numperson=0;
int change(string a){
	if(stringtoint.find(a)!=stringtoint.end()){
		return stringtoint[a];
	}else{
		stringtoint[a]=numperson;
		inttostring[numperson]=a;
		return numperson++;
	}
}

int main(){
	
	scanf("%d%d",&n,&k);
	string a,b;
	int w;
	for(int i=0;i<n;i++){
		cin>>a>>b>>w;
		int id1=change(a);
		int id2=change(b);
		g[id1][id2]+=w;
		g[id2][id1]+=w;
		weight[id1]+=w;
		weight[id2]+=w;
	}
	
	dfstrave();
	cout<<gang.size()<<endl;
	map<string,int>::iterator it;
	for(it=gang.begin();it!=gang.end();it++){
		cout<<it->first<<" "<<it->second<<endl;
	}
	
	
	return 0;
}

2.邻接矩阵版bfs

void bfs(int u){
	queue<int> q;
	q.push(u);
	inq[u]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int v=0;v<n;v++){
			if(inq[v]==false&&g[u][v]!=inf){
				q.push(v);
				inq[v]=true;
			}
		}
	}
}

void bfstrave(){
	for(int u=0;u<n;u++){
		if(inq[u]==false){
			bfs(u);
		}
	}
}

3.邻接表

const int maxv=100000;
int n,g[maxv][maxv];
bool inq[maxv]={false};

void bfs(int u){
	queue<int> q;
	q.push(u);
	inq[u]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int v=0;v<n;v++){
			if(inq[v]==false&&g[v][u]!=inf){
				q.push(v);
				inq[v]=true;
			}
		}
	}
}

4.带层号

void bfs(int s){
	queue<node> q;
	node start;
	start.layer=0;
	start.value=s;
	q.push(start);
	inq[start.value]=true;
	while(!q.empty()){
		node topnode=q.front();
		q.pop();
		int u=topnode.value;
		for(int i=0;i<adj[u].size();i++){
			node next=adj[u][i];
			next.layer=topnode.layer+1;
			if(inq[next.value]==false){
				q.push(next);
				inq[next.value]=true;
			}
		}
	}
}

5.Forwards on Weibo

#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

const int maxv=1010;
struct node{
	int id;
	int layer;
};
vector<node> adj[maxv];
bool inq[maxv]={false};

int bfs(int s,int l){
	int forwardnum=0;
	node start;
	start.id=s;
	start.layer=0;
	queue<node> q;
	q.push(start);
	inq[start.id]=true;
	while(!q.empty()){
		node topnode=q.front();
		q.pop();
		int id=topnode.id;
		for(int i=0;i<adj[id].size();i++){
			node now=adj[id][i];
			now.layer=topnode.layer+1;
			if(inq[now.id]==false&&now.layer<=l){
				q.push(now);
				inq[now.id]=true;
				forwardnum++;
			}
		}
	}
	return forwardnum++;
}

int main(){
	
	int n,l;
	scanf("%d%d",&n,&l);
	int follownum,id;
	node user;
	for(int i=1;i<=n;i++){
		user.id=i;
		scanf("%d",&follownum);
		for(int j=0;j<follownum;j++){
			scanf("%d",&id);
			adj[id].push_back(user);
		}
	}
	
	int numquery;
	scanf("%d",&numquery);
	int s;
	for(int i=0;i<numquery;i++){
		memset(inq,false,sizeof(inq));
		scanf("%d",&s);
		int numforward=bfs(s,l);
		printf("%d\n",numforward);
	}
	
	return 0;
}