[2018百度之星] 资格赛1006 三原色图 (最小生成树)

发表于 | 更新于 | 分类于 ， ， | 评论数： | 阅读次数：

链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=820&pid=1006

这题很简单，按照RG、BG的组合分别跑最小生成树，假如某一种情况无法构造出则抛弃那一种情况。同时给边打标记，最后再取k-(n+1)条最短的未添加到生成树里的边就行了。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;

typedef struct Node {
  int id, u, v, w;
  char c;
  friend bool operator<(Node a, Node b) {
    return a.w > b.w;
  }
}Node;
const int maxn = 110;
int n, m, eid;
int pre[maxn];
int vis[maxn<<2];
vector<Node> G[maxn];
priority_queue<Node> pq;

int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]);
}

bool unite(int x, int y) {
  x = find(x); y = find(y);
  if (x != y) {
    pre[y] = x;
    return 1;
  }
  return 0;
}

pair<int, bool> gao1(int k) {
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i < maxn; i++) pre[i] = i;
  while (!pq.empty()) pq.pop();
  int tot = 0, ret = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < G[i].size(); j++) {
      if(G[i][j].c == 'R' || G[i][j].c == 'G') {
        pq.push(G[i][j]);
      }
    }
  }
  while(!pq.empty()) {
    Node p = pq.top(); pq.pop();
    if(unite(p.u, p.v)) {
      tot++;
      ret += p.w;
      vis[p.id] = 1;
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < G[i].size(); j++) {
      if(!vis[G[i][j].id]) pq.push(G[i][j]);
    }
  }
  for(int i = 0; i < k - n + 1; i++) {
    ret += pq.top().w; pq.pop(); pq.pop();
  }
  return make_pair(ret, tot == n - 1);
}

pair<int, bool> gao2(int k) {
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i < maxn; i++) pre[i] = i;
  while (!pq.empty()) pq.pop();
  int tot = 0, ret = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < G[i].size(); j++) {
      if(G[i][j].c == 'B' || G[i][j].c == 'G') {
        pq.push(G[i][j]);
      }
    }
  }
  while(!pq.empty()) {
    Node p = pq.top(); pq.pop();
    if(unite(p.u, p.v)) {
      tot++;
      ret += p.w;
      vis[p.id] = 1;
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < G[i].size(); j++) {
      if(!vis[G[i][j].id]) pq.push(G[i][j]);
    }
  }
  for(int i = 0; i < k - n + 1; i++) {
    ret += pq.top().w; pq.pop(); pq.pop();
  }
  return make_pair(ret, tot == n - 1);
}

signed main() {
  // freopen("in", "r", stdin);
  int T, _ = 0;
  int u, v, w;
  char c[5];
  scanf("%d", &T);
  while(T--) {
    eid = 1;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) G[i].clear();
    for(int i = 0; i < m; i++) {
      scanf("%d%d%d%s",&u,&v,&w,c);
      G[u].push_back({eid, u, v, w, c[0]});
      G[v].push_back({eid++, v, u, w, c[0]});
    }
    pair<int, bool> tmp;
    printf("Case #%d:\n", ++_);
    for(int k = 1; k <= m; k++) {
      if(k < n - 1) {
        printf("-1\n");
        continue;
      }
      int ret = 0x7f7f7f7f;
      tmp = gao1(k);
      if(tmp.second) {
        ret = min(ret, tmp.first);
      }
      tmp = gao2(k);
      if(tmp.second) {
        ret = min(ret, tmp.first);
      }
      if(ret == 0x7f7f7f7f) printf("-1\n");
      else printf("%d\n", ret);
    }
  }
  return 0;
}