1. 首页
2. 连通图
3. 本页

HDU 5934 Bomb (Tarjan)

题意：~

思路：如果v能引爆u那么v向u建边。之后用Tarjin强连通缩点，变成有向无环图，将那些入度为0的点的集合求最小引爆带价。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
#define pb push_back
#define Key_value ch[ch[root][1]][0]
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
const double eps = 1e-8;
const double pi = acos (-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int M = 1000100;
const int MAXN = 1010;
const int MAXM = 1000010;

struct Edge
{
    int to, next;
} edge[MAXM];
int head[MAXN], tot;
int Low[MAXN], DFN[MAXN], Stack[MAXN], Belong[MAXN];
int index, top;
int scc;
bool Instack[MAXN];
int num[MAXN];

void addedge (int u, int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void Tarjan (int u)
{
    int v;
    Low[u] = DFN[u] = ++index;
    Stack[top++] = u;
    Instack[u] = true;
    for (int i = head[u]; ~i; i = edge[i].next)
    {
        v = edge[i].to;
        if (!DFN[v])
        {
            Tarjan (v);
            if (Low[u] > Low[v]) Low[u] = Low[v];
        }
        else if (Instack[v] && Low[u] > DFN[v])
            Low[u] = DFN[v];
    }
    if (Low[u] == DFN[u])
    {
        scc++;
        do
        {
            v = Stack[--top];
            Instack[v] = false;
            Belong[v] = scc;
            num[scc]++;
        }
        while (v != u);
    }
}

void solve (int N)
{
    MS (DFN, 0);
    MS (Instack, false);
    MS (num, 0);
    index = scc = top = 0;
    for (int i = 1; i <= N; ++i)
    {
        if (!DFN[i]) Tarjan (i);
    }
}
void init()
{
    tot = 0;
    MS (head, -1);
}

struct point
{
    LL x, y, r;
    int c;
} p[1050];
int du[1050];

bool booldis(point a, point b)
{
    if(a.r * a.r >= (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) return true;
    return false;
}

int main()
{
    int t;
    scanf("%d", &t);
    int casee=1;
    while(t--)
    {
        int n, x, y, r, c;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lld%lld%lld%d", &p[i].x, &p[i].y, &p[i].r, &p[i].c);
        }
        init();
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(i == j) continue;
                if(booldis(p[i], p[j])) addedge(i, j);
            }
        }
        solve(n);
        MS(du, 0);
        for(int i = 1; i <= n; ++i)
        {
            for(int j = head[i]; ~j; j = edge[j].next)
            {
                if(Belong[i] == Belong[edge[j].to])continue;
                du[Belong[edge[j].to]]++;  //in
            }
        }
        int ans = 0;
        for(int i = 1; i <= scc; ++i)
        {
            if(du[i] == 0)
            {
                int tmp = INF;
                for(int j = 1; j <= n; ++j)
                {
                    if(Belong[j] == i)
                    {
                        tmp = min(tmp, p[j].c);
                    }
                }
                ans += tmp;
            }
        }
        printf("Case #%d: %d\n",casee++,ans);
    }

    return 0;
}