HDU 5934 强联通分量

Bomb

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1853 Accepted Submission(s): 608

Problem Description

There are

Input

First line contains an integer

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum cost.

Sample Input

1 5 0 0 1 5 1 1 1 6 0 1 1 7 3 0 2 10 5 0 1 4

Sample Output

Case #1: 15

Source

2016年中国大学生程序设计竞赛（杭州）

思路：将给出的点之间连边，对每个强联通分量去最小值即可。

代码：

  1 ```C++
  2 #include<bits/stdc++.h>
  3 //#include<regex>
  4 #define db double
  5 #include<vector>
  6 #define ll long long
  7 #define vec vector<ll>
  8 #define Mt  vector<vec>
  9 #define ci(x) scanf("%d",&x)
 10 #define cd(x) scanf("%lf",&x)
 11 #define cl(x) scanf("%lld",&x)
 12 #define pi(x) printf("%d
",x)
 13 #define pd(x) printf("%f
",x)
 14 #define pl(x) printf("%lld
",x)
 15 #define MP make_pair
 16 #define PB push_back
 17 #define inf 0x3f3f3f3f3f3f3f3f
 18 #define fr(i, a, b) for(int i=a;i<=b;i++)
 19 const int N = 4e6 + 5;
 20 const int mod = 1e9 + 7;
 21 const int MOD = mod - 1;
 22 const db eps = 1e-18;
 23 const db PI = acos(-1.0);
 24 using namespace std;
 25 struct P {
 26     int f, to, nxt;
 27 } e[N];
 28 
 29 struct PP {
 30     int x, y, r, c;
 31 } a[N];
 32 int hea[3500];
 33 int n, cnt, sig, tt, cont;
 34 int deg[3500], sta[3500], col[3500], vis[3500], low[3500], dfn[3500], need[3500], contz[3500];
 35 
 36 void add(int f, int to) {//建边
 37     e[cont].to = to;
 38     e[cont].f = f;
 39     e[cont].nxt = hea[f];
 40     hea[f] = cont++;
 41 }
 42 
 43 void tarjan(int u) {//强联通分量
 44     vis[u] = 1;
 45     low[u] = dfn[u] = cnt++;
 46     sta[++tt] = u;
 47     for (int i = hea[u]; i != -1; i = e[i].nxt) {
 48         int v = e[i].to;
 49         if (vis[v] == 0) tarjan(v);
 50         if (vis[v] == 1) low[u] = min(low[u], low[v]);
 51     }
 52     if (dfn[u] == low[u]) {
 53         sig++;
 54         do {
 55             col[sta[tt]] = sig;
 56             vis[sta[tt]] = -1;
 57         } while (sta[tt--] != u);
 58     }
 59 }
 60 
 61 void cal() {
 62     cnt = 1;
 63     sig = 0;
 64     tt = -1;
 65     memset(dfn, 0, sizeof(dfn));memset(col, 0, sizeof(col));memset(vis, 0, sizeof(vis));
 66     memset(sta, 0, sizeof(sta));memset(low, 0, sizeof(low));memset(deg, 0, sizeof(deg));
 67     memset(contz, 0x3f3f3f3f, sizeof(contz));
 68     for (int i = 0; i < n; i++) if (!vis[i]) tarjan(i);
 69     for (int i = 0; i < cont; i++) {
 70         int u = e[i].f;
 71         int v = e[i].to;
 72         if (col[u] != col[v]) deg[col[v]]++;
 73     }
 74     for (int i = 0; i < n; i++) if (!deg[col[i]]) contz[col[i]] = min(contz[col[i]], a[i].c);
 75     int ans = 0;
 76 
 77     for (int i = 1; i <= sig; i++) if (!deg[i]) ans += contz[i];
 78     pi(ans);
 79 }
 80 
 81 int main() {
 82     int t;
 83     ci(t);
 84     for (int ii = 1; ii <= t; ii++) {
 85         ci(n);
 86         for (int i = 0; i < n; i++) scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].r, &a[i].c);
 87         cont = 0;
 88         memset(hea, -1, sizeof(hea));
 89         for (int i = 0; i < n; i++) {
 90             for (int j = 0; j < n; j++) {
 91                 ll tmp = a[i].x - a[j].x;
 92                 ll tmp2 = a[i].y - a[j].y;
 93                 ll d1 = tmp * tmp + tmp2 * tmp2;
 94                 ll d2 = 1ll * a[i].r * a[i].r;
 95                 if (d1 <= d2) add(i, j);
 96             }
 97         }
 98         printf("Case #%d: ", ii);
 99         cal();
100     }
101     return 0;
102 }
103 
104 ```

  1 #include<bits/stdc++.h>
  2 //#include<regex>
  3 #define db double
  4 #include<vector>
  5 #define ll long long
  6 #define vec vector<ll>
  7 #define Mt  vector<vec>
  8 #define ci(x) scanf("%d",&x)
  9 #define cd(x) scanf("%lf",&x)
 10 #define cl(x) scanf("%lld",&x)
 11 #define pi(x) printf("%d
",x)
 12 #define pd(x) printf("%f
",x)
 13 #define pl(x) printf("%lld
",x)
 14 #define MP make_pair
 15 #define PB push_back
 16 #define inf 0x3f3f3f3f3f3f3f3f
 17 #define fr(i, a, b) for(int i=a;i<=b;i++)
 18 const int N = 4e6 + 5;
 19 const int mod = 1e9 + 7;
 20 const int MOD = mod - 1;
 21 const db eps = 1e-18;
 22 const db PI = acos(-1.0);
 23 using namespace std;
 24 struct P {
 25     int f, to, nxt;
 26 } e[N];
 27 
 28 struct PP {
 29     int x, y, r, c;
 30 } a[N];
 31 int hea[3500];
 32 int n, cnt, sig, tt, cont;
 33 int deg[3500], sta[3500], col[3500], vis[3500], low[3500], dfn[3500], need[3500], contz[3500];
 34 
 35 void add(int f, int to) {//建边
 36     e[cont].to = to;
 37     e[cont].f = f;
 38     e[cont].nxt = hea[f];
 39     hea[f] = cont++;
 40 }
 41 
 42 void tarjan(int u) {//强联通分量
 43     vis[u] = 1;
 44     low[u] = dfn[u] = cnt++;
 45     sta[++tt] = u;
 46     for (int i = hea[u]; i != -1; i = e[i].nxt) {
 47         int v = e[i].to;
 48         if (vis[v] == 0) tarjan(v);
 49         if (vis[v] == 1) low[u] = min(low[u], low[v]);
 50     }
 51     if (dfn[u] == low[u]) {
 52         sig++;
 53         do {
 54             col[sta[tt]] = sig;
 55             vis[sta[tt]] = -1;
 56         } while (sta[tt--] != u);
 57     }
 58 }
 59 
 60 void cal() {
 61     cnt = 1;
 62     sig = 0;
 63     tt = -1;
 64     memset(dfn, 0, sizeof(dfn));memset(col, 0, sizeof(col));memset(vis, 0, sizeof(vis));
 65     memset(sta, 0, sizeof(sta));memset(low, 0, sizeof(low));memset(deg, 0, sizeof(deg));
 66     memset(contz, 0x3f3f3f3f, sizeof(contz));
 67     for (int i = 0; i < n; i++) if (!vis[i]) tarjan(i);
 68     for (int i = 0; i < cont; i++) {
 69         int u = e[i].f;
 70         int v = e[i].to;
 71         if (col[u] != col[v]) deg[col[v]]++;
 72     }
 73     for (int i = 0; i < n; i++) if (!deg[col[i]]) contz[col[i]] = min(contz[col[i]], a[i].c);
 74     int ans = 0;
 75 
 76     for (int i = 1; i <= sig; i++) if (!deg[i]) ans += contz[i];
 77     pi(ans);
 78 }
 79 
 80 int main() {
 81     int t;
 82     ci(t);
 83     for (int ii = 1; ii <= t; ii++) {
 84         ci(n);
 85         for (int i = 0; i < n; i++) scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].r, &a[i].c);
 86         cont = 0;
 87         memset(hea, -1, sizeof(hea));
 88         for (int i = 0; i < n; i++) {
 89             for (int j = 0; j < n; j++) {
 90                 ll tmp = a[i].x - a[j].x;
 91                 ll tmp2 = a[i].y - a[j].y;
 92                 ll d1 = tmp * tmp + tmp2 * tmp2;
 93                 ll d2 = 1ll * a[i].r * a[i].r;
 94                 if (d1 <= d2) add(i, j);
 95             }
 96         }
 97         printf("Case #%d: ", ii);
 98         cal();
 99     }
100     return 0;
101 }