题目地址
题目不难,知道tarjan的功能就能出了。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
const int eg = 1e6+5;
int head[maxn], dfn[maxn], low[maxn];
int st[maxn], ins[maxn], c[maxn];
vector<int>ssc[maxn];
int n, m, tot, num, top, cnt;
struct node{
int v, to;
}cc[eg];
void add(int u, int v) {
tot++;
cc[tot].to = head[u];
cc[tot].v = v;
head[u] = tot;
}
void tarjan(int x) {
dfn[x] = low[x] = ++num;
st[++top] = x, ins[x] = 1;
for(int i = head[x]; i; i = cc[i].to) {
int v = cc[i].v;
if(!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(ins[v])
low[x] = min(low[x], dfn[v]);
}
if(dfn[x] == low[x]) {
cnt++;int y;
do{
y = st[top--], ins[y] = 0;
c[y] = cnt, ssc[cnt].push_back(y);
}while(x != y);
}
}
struct P{
double x, y;
double r;int c;
}p[maxn];
double dis(P a, P b) {
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
struct NP{
int to, v;
}P[eg];
int np_head[maxn], np_tot;
void add_c(int x, int y) {
np_tot++;
P[np_tot].to = np_head[x];
P[np_tot].v = y;
np_head[x] = np_tot;
}
int val[maxn], in[maxn];
void init() {
num = np_tot = cnt = tot = top = 0;
for(int i = 1; i <= n; i++) {
ins[i] = dfn[i] = in[i] = head[i] = np_head[i] = 0;
ssc[i].clear();
val[i] = 100000;
}
}
int T = 0;
void solve() {
scanf("%d", &n);
init();
for(int i = 1; i <= n; i++) {
scanf("%lf%lf%lf%d", &p[i].x, &p[i].y, &p[i].r, &p[i].c);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) continue;
if(dis(p[i], p[j]) <= p[i].r*p[i].r) add(i, j);
}
}
for(int i = 1; i <= n; i++) {
if(!dfn[i]) tarjan(i);
}
for(int i = 1; i <= cnt; i++) {
for(int j = 0; j < ssc[i].size(); j++) {
val[i] = min(val[i], p[ssc[i][j]].c);
}
}
for(int i = 1; i <= n; i++) {
for(int j = head[i]; j; j = cc[j].to) {
int v = cc[j].v;
if(c[i] == c[v]) continue;
add_c(c[i], c[v]);
in[c[v]]++;
}
}
long long res = 0;
for(int i = 1; i <= cnt; i++) {
if(in[i] == 0){ res += val[i];
}
}
printf("Case #%d: %lld\n", ++T, res);
}
int main() {
int Case;
scanf("%d", &Case);
while(Case--)
solve();
return 0;
}