列出连通集

给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。

输入格式

输入第1行给出2个整数N(0<N10)N(0<N≤10)和E,分别是图的顶点数和边数。随后E行,每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式

按照"{ v1 v2 … vk}"的格式,每行输出一个连通集。先输出DFS的结果,再输出BFS的结果。

输入样例

8 6
0 7
0 1
2 0
4 1
2 4
3 5

输出样例

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

ac代码

#include<iostream>
#include<queue>
#define maxinte 10
using namespace std;
void BuildMGraph();
void printdb();
void DFS(int);
void BFS(int);
int MGraph[maxinte][maxinte],Ne,Nv;
bool visited[maxinte];
int main(){
    BuildMGraph();
    printdb();
}
void BuildMGraph(){
    cin>>Nv>>Ne;
    int v1,v2;
    for(int i=0;i<Nv;i++)for(int j=0;j<Nv;j++)MGraph[i][j]=0;
    for(int i=0;i<Ne;i++){
        cin>>v1>>v2;
        MGraph[v1][v2]=MGraph[v2][v1]=1;
    }
}
void printdb(){
    for(int j=0;j<Nv;j++)visited[j]=false;
    for(int i=0;i<Nv;i++)
        if(!visited[i]){
            cout<<"{ ";
            DFS(i);
            cout<<"}"<<endl;
        }
    for(int j=0;j<Nv;j++)visited[j]=false;
    for(int i=0;i<Nv;i++)
        if(!visited[i]){
            cout<<"{ ";
            BFS(i);
            cout<<"}"<<endl;
        }
}
void DFS(int v){
    visited[v]=true;
    cout<<v<<' ';
    for(int i=0;i<Nv;i++)
        if(MGraph[v][i]!=0&&!visited[i])DFS(i);
}
void BFS(int v){
    queue<int> q;
    int w;
    q.push(v);
    visited[v]=true;
    while(!q.empty()){
        v=q.front(),q.pop();
        cout<<v<<' ';
        for(int i=0;i<Nv;i++)
            if(MGraph[v][i]!=0&&!visited[i]){
                visited[i]=true;
                q.push(i);
            }
    }
}

Forwards on Weibo

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.

Input Specification

Each input file contains one test case. For each case, the first line contains 2 positive integers: N(1000)N (≤1000), the number of users; and L (≤6), the number of levels of indirect followers that are counted. Hence it is assumed that all the users are numbered from 1 to N. Then N lines follow, each in the format:

M[i] user_list[i]

where M[i](100)M[i] (≤100) is the total number of people that user[i] follows; and user_list[i] is a list of the M[i] users that followed by user[i]. It is guaranteed that no one can follow oneself. All the numbers are separated by a space. Then finally a positive K is given, followed by K UserID’s for query.

Output Specification

For each UserID, you are supposed to print in one line the maximum potential amount of forwards this user can trigger, assuming that everyone who can view the initial post will forward it once, and that only L levels of indirect followers are counted.

Sample Input

7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6

Sample Output

4
5

题意分析

本题输入给出的是关注的人,注意转发微博是关注的人转发被关注的人,所以边的方向应该是关注指向被关注

  • 可以理解为关注的人本身是不知道有什么人关注了他自己的)
  • 输出是是在给定层数l限制下最多能有多少人转发
    • 即与给定顶点之间路径长度不超过l的结点个数

ac代码

#include<iostream>
#include<queue>
#define MaxUsers 1000
using namespace std;
typedef int Vertex;
typedef struct AdjVNode *PtrToAdjVNode;
typedef struct LGNode *PtrToLGNode;
typedef struct Vnode AdjList[MaxUsers+1];
typedef PtrToLGNode LGraph;
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};
struct Vnode{
    PtrToAdjVNode FirstEdge;
};
struct LGNode{
    int Nv,Ne;
    AdjList G;
};
LGraph CreatelGraph(int);
void InsertEdge(LGraph,int,int);
LGraph BuildLGraph(int);
void ForwardsonWeibo(LGraph,int,bool*);
int BFS(LGraph,int,int,bool*);
int main(int argc,char*argv[]) {
    int l,n;
    cin>>n>>l;
    bool visited[n+1];
    LGraph L=BuildLGraph(n);
    ForwardsonWeibo(L,l,visited);
}
LGraph BuildLGraph(int n){
    int user,userl;
    LGraph L=CreatelGraph(n);
    for(int i=1;i<=n;i++){
        cin >> user;
        for(int j=1; j <=user; j++){
            cin>>userl;
            InsertEdge(L,i,userl);
        }
    }
    return L;
}
LGraph CreatelGraph(int n){
    auto L=new struct LGNode;
    for(int i=0;i<=n;i++)L->G[i].FirstEdge= nullptr;
    L->Nv=n,L->Ne=0;
    return L;
}
void InsertEdge(LGraph L,int user,int userl){
    auto newnode=new struct AdjVNode;
    newnode->AdjV=user;
    newnode->Next=L->G[userl].FirstEdge;
    L->G[userl].FirstEdge=newnode;
    L->Ne++;
}
void ForwardsonWeibo(LGraph L,int l,bool*visited){
    int n,v;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v;
        for(int j=1;j<=L->Nv;j++)visited[j]= false;
        cout<<BFS(L,v,l,visited)<<endl;
    }
}
int BFS(LGraph L,int v,int l,bool*visited){
    int last=v,tail,level=0,count=0;
    PtrToAdjVNode w;
    queue<int> q;
    q.push(v);
    visited[v]=true;
    while(!q.empty()){
        v=q.front(),q.pop();
        w=L->G[v].FirstEdge;
        while(w) {
            if (!visited[w->AdjV]) {
                q.push(w->AdjV);
                visited[w->AdjV] = true, count++, tail = w->AdjV;
            }
            w = w->Next;
        }
        if(v==last)level++,last=tail;
        if(level==l)break;
    }
    return count;
}

旅游规划

有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。

输入格式

输入说明:输入数据的第1行给出4个正整数N、M、S、D,其中N(2N500)N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N−1);M是高速公路的条数;S是出发地的城市编号;D是目的地的城市编号。随后的M行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。

输出格式

在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。

输入样例

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例

3 40

分析

  • 城市为结点
  • 公路为边
    • 权重1:距离
    • 权重2:收费
  • 单源最短路
    • Dijkstra——距离
    • 等距离时按收费更新

核心算法

void Dijkstra(Vertex S)
{
    while(1)
    {
        v=未收录顶点中dist最小者;
        if(这样的v不存在)
            break;
        collected[w]==true;
        for(v的每个邻接点w)
            if(collected[w]==false)
                if(dist[v]+E(v,w)<dist[w])
                {
                    dist[w]=dist[v]+E(v,w);
                    path[w]=v;
                    cost[w]=cast[v]+C(v,w);
                }
                else if((dist[v]+E(v,w)==dist[w])
                        &&(cost[v]+C(v,w)<cost[w]))
                {
                    cost[w]=cost[v]+C(v,w);
                }
    }
}

其他类似问题

  • 要求数最短路径有多少条
    • count[s]=1;
    • 如果找到更短路:count[w]=count[v];
    • 如果找到等长路:count[w]+=count[v];
  • 要求边数最少得最短路(本质上等价于dist,只不过每新增一条边的权重均为1)
    • count[s]=0;
    • 如果找到更短路:count[w]=count[v]+1;
    • 如果找到等长路:count[w]=count[v]+1;

ac代码

#include<iostream>
#define MaxCities 500
#define INFINITY 65535
using namespace std;
typedef struct{
    int length,price;
}highway;
highway G[MaxCities][MaxCities];
bool collected[MaxCities]={false};
int dist[MaxCities],price[MaxCities];
void Buildgraph(int,int);
int FindMindistprice(int);
void Dijkstra(int,int);
void selectpath(int,int,int);
int main(int argc,char*argv[]) {
    int N,M,S,D;
    cin>>N>>M>>S>>D;
    Buildgraph(M,N);
    selectpath(N,S,D);
}
void Buildgraph(int m,int n){
    int c1,c2;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++){
        G[i][j].length=G[i][j].price=INFINITY;
        G[j][i]=G[i][j];
    }
    for(int i=0;i<m;i++){
        cin>>c1>>c2>>G[c1][c2].length>>G[c1][c2].price;
        G[c2][c1]=G[c1][c2];
    }
}
void selectpath(int n,int s,int d){
    for(int i=0;i<n;i++)dist[i]=price[i]=INFINITY;
    Dijkstra(s,n);
    cout<<dist[d]<<' '<<price[d]<<endl;
}
int FindMindistprice(int n){
    int mind=INFINITY,minp=INFINITY,mini=0;
    for(int i=0;i<n;i++)if(!collected[i]&&(mind>=dist[i]||(mind==dist[i]&&minp>price[i])))
        mind=dist[i],mini=i,minp=price[i];
    if(mind<(int)INFINITY)return mini;
    return -1;
}
void Dijkstra(int s,int n){
    for(int i=0;i<n;i++)dist[i]=G[s][i].length,price[i]=G[s][i].price;
    collected[s]=true,dist[s]=price[s]=0;
    while(true){
        int v=FindMindistprice(n);
        collected[v]=true;
        if(v<0)break;
        for(int i=0;i<n;i++)if(!collected[i]&&G[v][i].length<(int)INFINITY)
            if (dist[i]>dist[v]+G[v][i].length||(dist[i]==dist[v]+G[v][i].length&&price[i]>price[v]+G[v][i].price))
                dist[i]=dist[v]+G[v][i].length,price[i]=price[v]+G[v][i].price;
    }
}