Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

There are N mines in an old battlefield. Each mine affects an axis-parallel square area depending on its performance. Assume that the location of the mine is the center of the square area. When a mine explodes, all mines in the square area of the explosion will explode as well. As a chain reaction, all the mines in the square area of the following explosion will also explode. Assume that when a mine is exploding, a mine on the edge of the exploding square area will also explode.

In the following figure, if mine 4 initiates, mines 3 and 6 will explode. If mine 1 initiates, mine 4 will explode. The following explosion will result mines 3 and 6 to explode. Therefore, initiating mines 1, 2, and 5 will cause all the mines to explode.

Given N mines with their explosion performance as square areas in a two-dimensional plane, write a program that determines the minimum number of mines that needs to be initiated to explode all given mines.

Input 

Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer N ( 3N2, 000), which represents the number of mines. In the following N lines, each line contains three integers x, y and d, where x and y are the coordinates of the mine in the plane and d is the size of one side of the square which representing the explosion performance ( 1x, y10, 000, 000, 1d1, 000, 000).

Output 

Your program is to write to standard output. Print exactly one line for each test case. Print the minimum number of mines that needs to be initiated to explode all given mines.

The following shows sample input and output for two test cases.

Sample Input 

2
6
6 11 10
10 17 4
12 10 4
10 7 6
5 4 6
12 5 2
4
6 7 8
9 10 4
11 5 4
15 9 8

Sample Output 

3
2

---

題目描述：
一個礦坑的引爆，引爆點都位於正方形中間，如果引爆一個礦坑時，涉及另一個礦坑的引爆點，則會再次引起爆炸。求最少引爆次數(引爆第一個)的次數。

題目解法：
其實就與骨牌遊戲很像，推誰誰會倒，求最少推的次數使其全倒。
那如果圖是 DAG(有向無環圖)，那麼簡單地會想到 indeg = 0 的點個數，恰好就是答案。
但圖有可能不是 DAG，那麼使用 SCC 將強連通元件縮成一點，原圖就可以轉換成 DAG。
就可以得到答案了。

建圖前先排序一次，然後減少建圖的成本。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
struct E {
    int x, y, d;
    bool operator<(const E &a) const {
        return x < a.x;
    }
} D[10000];
#define maxN 4096
vector<int> g[maxN];
int vfind[maxN], findIdx;
int stk[maxN], stkIdx;
int in_stk[maxN], visited[maxN];
int scc_cnt;
int contract[maxN];
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd]; // back edge
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(!visited[*it])
            mn = min(mn, scc(*it));
        if(in_stk[*it])
            mn = min(mn, vfind[*it]);
    }
    if(mn == vfind[nd]) {
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
        } while(stk[stkIdx--] != nd);
        scc_cnt++;
    }
    return mn;
}
int main() {
    int t, n, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].d);
        sort(D, D+n);
        int indeg[2005] = {}, x, y, d;
        for(i = 0; i < n; i++) {
            g[i].clear();
            d = D[i].d;
            x = D[i].x;
            y = D[i].y;
            for(j = i+1; j < n; j++) {
                if(D[j].x - x > d/2.0)
                    break;
                if(y-d/2.0 <= D[j].y && D[j].y <= y+d/2.0)
                    g[i].push_back(j);
            }
            for(j = i-1; j >= 0; j--) {
                if(x - D[j].x > d/2.0)
                    break;
                if(y-d/2.0 <= D[j].y && D[j].y <= y+d/2.0)
                    g[i].push_back(j);
            }
        }
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        scc_cnt = 0;
        for(i = 0; i < n; i++) {
            if(!visited[i]) {
                findIdx = stkIdx = 0;
                scc(i);
            }
        }
        for(i = 0; i < n; i++) {//become DAG
            x = contract[i];
            //printf("contract %d\n", x);
            for(vector<int>::iterator it = g[i].begin();
                it != g[i].end(); it++) {
                y = contract[*it];
                if(x != y)
                    indeg[y]++;
            }
        }
        int ret = 0;
        for(i = 0; i < n; i++)
            if(indeg[i] == 0 && i == contract[i])
                ret++;
        printf("%d\n", ret);
    }
    return 0;
}