本文共 3141 字，大约阅读时间需要 10 分钟。
其实就是bfs，不过也可以写成最短路，因为权重为1，可以用Spira解。
1 /* 3832 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int maxn = 205; 43 const int maxe = maxn*maxn*2; 44 const int INF = 1e7; 45 int X[maxn], Y[maxn], R[maxn]; 46 int dis[maxn], D[3][maxn]; 47 bool inS[maxn]; 48 int V[maxe], nxt[maxe]; 49 int head[maxn], head_[maxn], n, m; 50 51 void addEdge(int u, int v) { 52 V[m] = v; 53 nxt[m] = head[u]; 54 head[u] = m++; 55 56 V[m] = u; 57 nxt[m] = head[v]; 58 head[v] = m++; 59 } 60 61 typedef struct node_t { 62 int u, v, w; 63 64 node_t() {} 65 66 node_t(int u_, int v_, int w_): 67 u(u_), v(v_), w(w_) {} 68 69 friend bool operator< (const node_t& a, const node_t& b) { 70 return a.w > b.w; 71 } 72 } node_t; 73 74 void forward(priority_queue & Q, int u) { 75 int& k = head_[u]; 76 77 if (k != -1) { 78 Q.push(node_t(u, V[k], dis[u]+1)); 79 k = nxt[k]; 80 } 81 } 82 83 void Spira(int s) { 84 priority_queue Q; 85 node_t nd; 86 int cnt = 1; 87 88 memset(inS, false, sizeof(inS)); 89 rep(i, 1, n+1) dis[i] = INF; 90 dis[s] = 0; 91 inS[s] = true; 92 forward(Q, s); 93 94 while (!Q.empty()) { 95 nd = Q.top(); 96 Q.pop(); 97 forward(Q, nd.u); 98 if (!inS[nd.v]) { 99 inS[nd.v] = true;100 dis[nd.v] = nd.w;101 if (++cnt == n)102 break;103 forward(Q, nd.v);104 }105 }106 }107 108 int main() {109 ios::sync_with_stdio(false);110 #ifndef ONLINE_JUDGE111 freopen("data.in", "r", stdin);112 freopen("data.out", "w", stdout);113 #endif114 115 int t;116 int mn, ans;117 118 scanf("%d", &t);119 while (t--) {120 scanf("%d", &n);121 rep(i, 1, n+1)122 scanf("%d %d %d", &X[i], &Y[i], &R[i]);123 memset(head, -1, sizeof(head));124 m = 0;125 rep(i, 1, n+1) {126 rep(j, 1, i) {127 if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]) <= (R[i]+R[j])*(R[i]+R[j])) {128 addEdge(i, j);129 }130 }131 }132 133 memcpy(head_, head, sizeof(head));134 Spira(1);135 memcpy(D[0], dis, sizeof(dis));136 137 memcpy(head_, head, sizeof(head));138 Spira(2);139 memcpy(D[1], dis, sizeof(dis));140 141 memcpy(head_, head, sizeof(head));142 Spira(3);143 memcpy(D[2], dis, sizeof(dis));144 145 mn = INF;146 rep(i, 1, n+1)147 mn = min(mn, D[0][i]+D[1][i]+D[2][i]);148 149 ans = (mn==INF) ? -1:n-mn-1;150 printf("%d\n", ans);151 }152 153 #ifndef ONLINE_JUDGE154 printf("time = %d.\n", (int)clock());155 #endif156 157 return 0;158 }
转载于:https://www.cnblogs.com/bombe1013/p/4911328.html