Home PAT 1034 Head of a Gang
Post
Cancel

PAT 1034 Head of a Gang

Link

最后要按照 name 的字典序排序, 否则测试点 2、5 过不了.

几个需要注意的地方:

  1. 在输入边权的时候, 可能有重复输入的情形, 例如在前面已经输入了 s1 s2 t1, 后面又出现了 s1 s2 t2, 这时候就不能直接 g[s1][s2]=t2, 因为这样会覆盖前面的边权. 所以, 最好写成 g[s1][s2]+=t2.
  2. DFS 的时候, 需要考虑到存在环的情形.
    • 如果图中无环, 仅仅只考虑连通分量, 那么写成下面这样是可以的:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      
      // in main
      {
          for(...){
              if(!v[i]){
                  v[i]=true;
                  DFS(i,...);
              }
          }
      }
      void DFS(int x,int &head,int &member,int &weight){
          member++;
          if(w[x]>w[head]) head=x;
          for(int i=1;i<=num;++i)
              if(g[x][i]&&!v[i]){
                  weight+=g[x][i];
                  v[i]=true;
                  DFS(i,head,member,weight);
              }
      }
      

      也就是说, 利用 v[i] (是否访问过该节点) 来判断是否需要遍历这个点.

    • 如果图中可能有环, 那么上面的代码就会出现一个问题: 从点 s1 出发, for 循环依次遍历与 s1 有边连接的每个点, 这里假设有 s2s3, 并且 s2s3 的前面被遍历. 由于 s1s3 之前就被设置为 v[s1]=true 了, 因此当依次访问与 s3 相邻的节点时, 一定不会访问 s1. 而 s2s3 是有边相连的, 即 s1, s2, s3 构成了一个环, 那么这样做只会计算 e(s1, s2)e(s2, s3), 而不会加上 e(s3, s1). 所以 if 里不能写上 !v[i], 而 !v[i] 仅用于判断是否需要 DFS. 正确代码如下:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      
      void DFS(int x,int &head,int &member,int &weight){
          v[x]=true;
          member++;
          if(w[x]>w[head]) head=x;
          for(int i=1;i<=num;++i)
              if(g[x][i]){
                  weight+=g[x][i];
                  g[x][i]=g[i][x]=0;
                  if(!v[i]) DFS(i,head,member,weight);
              }
      }
      

最终的 AC 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;
const int N=26*26*26;
int n,k,num;
int g[N][N],w[N];
bool v[N];
unordered_map<string,int>idmap;
unordered_map<int,string>strmap;
map<string,int>ans;
void DFS(int x,int &head,int &member,int &weight){
    v[x]=true;
    member++;
    if(w[x]>w[head]) head=x;
    for(int i=1;i<=num;++i)
        if(g[x][i]){
            weight+=g[x][i];
            g[x][i]=g[i][x]=0;
            if(!v[i]) DFS(i,head,member,weight);
        }
}
inline int getId(string name){
    int p;
    if(idmap.count(name)) p=idmap[name];
    else{
        idmap[name]=++num;
        p=num;
    }
    strmap[p]=name;
    return p;
}
int main() {
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        string name1,name2;
        int time;
        cin>>name1>>name2>>time;
        int p1=getId(name1),p2=getId(name2);
        w[p1]+=time;
        w[p2]+=time;
        //最好写成这种形式!
        g[p1][p2]+=time;
        g[p2][p1]+=time;
    }
    for(int i=1;i<=num;++i)
        if(!v[i]){
            int head=0,member=0,weight=0;
            DFS(i,head,member,weight);
            if(member>2&&weight>k)
                ans[strmap[head]]=member;
        }
    cout<<ans.size()<<endl;
    for(auto it=ans.begin();it!=ans.end();++it)
        cout<<it->first<<" "<<it->second<<endl;
    return 0;
}
This post is licensed under CC BY 4.0 by the author.