图的遍历 | 1034 map处理输入数据，连通块判断 - 开发语言

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

这题写得比较痛苦。首先有点不在状态，其次题目比较难读懂。

“Gang”成立的两个条件：①成员数大于两个 ②边权总和大于阈值K

首先，在录数据的时候通过 map 或者 字符串哈希 建立string到int的映射。

然后，这个题的数据结构其实是 带权无向图 。在录数据的时候就要处理好点权和边权。

最后，对所有顶点做一遍dfs，汇总边权，找出最大点权和最大点权所在的点，把数据录进ans里。

注意的点一个是环路边权的汇总。方法是在dfs中通过 先加边权 再 判断vis是否遍历过 。此时又要注意用不搜前驱点的dfs结果，及dfs(p,s) //p是前驱点，s是当前点

还有一个 是邻接数组要开大一点。虽然给出的图的边数是小于1000，但是顶点数不一定。

#include <stdio.h>

#include <memory.h>

#include <math.h>

#include <string>

#include <vector>

#include <set>

#include <stack>

#include <queue>

#include <algorithm>

#include <map>

#define I scanf

#define OL puts

#define O printf

#define F(a,b,c) for(a=b;a<c;a++)

#define FF(a,b) for(a=0;a<b;a++)

#define FG(a,b) for(a=b-1;a>=0;a--)

#define LEN 10000

#define MAX 0x06FFFFFF

#define V vector<int>

using namespace std;

string ID2name[LEN];

map<string,int> name2ID;

int g[LEN][LEN];

int nID=;

int w[LEN];

int vis[LEN];

int cnt;

int maxV;

int maxID;

int gang[LEN];

int sum;

set<string> ans;

int getID(string s){

    int id=name2ID[s];

    if(id){

        return id;

    }else{

        name2ID[s]=nID;

        ID2name[nID]=s;

        return nID++;

    }

}

void dfs(int p,int s){

    vis[s]=;

    cnt++;

    if(w[s]>maxV){

        maxV=w[s];

        maxID=s;

    }

    for(int i=;i<nID;i++) if(g[s][i]> && i!=p){

        sum+=g[s][i];

        if(vis[i]) continue;

        dfs(s,i);

    }

}

int main(){

//    freopen("D:\\CbWorkspace\\PAT\\图的遍历\\1034_2.txt","r",stdin);

    int n,k,i,j;

    I("%d%d",&n,&k);

    FF(i,n){

        char buf[];

        I("%s",buf);

        string a(buf);

        I("%s",buf);

        string b(buf);

        I("%d",&j);

        int ai=getID(a);

        int bi=getID(b);

        g[ai][bi]+=j;

        g[bi][ai]+=j;

        w[ai]+=j;

        w[bi]+=j;

    }

    F(i,,nID+) if(!vis[i]){

        cnt=;

        maxV=-;

        sum=;

        dfs(-,i);        //深搜

        if(cnt> && sum>k){

            ans.insert(ID2name[maxID]);

            gang[maxID]=cnt;

        }

    }

    printf("%d\n",ans.size());

    set<string>::iterator it=ans.begin();

    while(it!=ans.end()){

        printf("%s %d\n",it->c_str(),gang[name2ID[*it]]);

        it++;

    }

    return ;

}