比赛-Round (10 Jul)

1. 无线通讯网

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <math.h>
 4 
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 
 9 const int _N = 600;
10 
11 LL P, S;
12 LL Dad[_N], dis[_N][_N], A[_N*_N], X[_N], Y[_N];
13 bool mk[_N];
14 
15 LL _fun(LL val) { return val * val; }
16 
17 LL GetDad(LL v) { return Dad[v] == v ? v : Dad[v] = GetDad(Dad[v]); }
18 
19 bool Check(LL lim)
20 {
21     LL i, j;
22     for (i = 1; i <= P; ++i) Dad[i] = i, mk[i] = false;
23     for (i = 1; i <= P; ++i)
24         for (j = 1; j <= P; ++j)
25             if (i != j && dis[i][j] <= A[lim]) {
26                 LL t1 = GetDad(i), t2 = GetDad(j);
27                 if (t1 != t2) Dad[t1] = t2;
28             }
29     LL cnt = 0;
30     for (i = 1; i <= P; ++i) {
31         LL tmp = GetDad(i);
32         if (!mk[tmp]) mk[tmp] = true, ++cnt;
33     }
34     return cnt <= S;
35 }
36 
37 int main()
38 {
39     freopen("wireless.in", "r", stdin);
40     freopen("wireless.out", "w", stdout);
41     LL i, j, Acnt = 0;
42     scanf("%lld%lld", &S, &P);
43     for (i = 1; i <= P; ++i) scanf("%lld%lld", &X[i], &Y[i]);
44     for (i = 1; i <= P; ++i)
45         for (j = 1; j <= P; ++j)
46             if (i != j) A[++Acnt] = dis[i][j] = _fun(X[i]-X[j]) + _fun(Y[i]-Y[j]);
47     A[++Acnt] = 0;
48     sort(A+1, A+1+Acnt);
49     LL l = 1, r = Acnt;
50     while (l <= r) {
51         LL mid = l+r >> 1;
52         if (Check(mid)) r = mid - 1;
53         else l = mid + 1;
54     }
55     printf("%.2lf
", sqrt(A[l]));
56     
57     return 0;
58 }

View Code

2. 混合图

 1 #include <stdio.h>
 2 #include <vector>
 3 #include <queue>
 4 
 5 using namespace std;
 6 
 7 const int _N = 120000;
 8 
 9 queue<int> Q;
10 vector<int> G[_N];
11 
12 int ind[_N], pos[_N];
13 
14 inline void Ins(int a, int b) { G[a].push_back(b); ++ind[b]; return; }
15 
16 int main()
17 {
18     int N, i, M1, M2, a, b;
19     scanf("%d%d%d", &N, &M1, &M2);
20     for (i = 1; i <= M1; ++i)
21         scanf("%d%d", &a, &b), Ins(a, b);
22     for (i = 1; i <= N; ++i) {
23         if (!ind[i]) Q.push(i);
24         pos[i] = N+1;
25     }
26     int cnt = 0;
27     while (!Q.empty()) {
28         int t = Q.front();
29         pos[t] = ++cnt;
30         Q.pop();
31         for (i = G[t].size()-1; i >= 0; --i)
32             if(!--ind[G[t][i]]) Q.push(G[t][i]);
33     }
34     for (i = 1; i <= M2; ++i) {
35         scanf("%d%d", &a, &b);
36         if (pos[a] > pos[b]) swap(a, b);
37         printf("%d %d
", a, b);
38     }
39     return 0;
40 }

View Code

3. 小K的农场

非常重要。学到了新操作：SPFA 的 SLF, LLL 优化，以及在判负环时的 DFS 优化，还有权值无意义时（只判负环时）的 DFS, dis[i] = 0 优化。

详细见 SPFA 模板那篇随笔（http://www.cnblogs.com/ghcred/p/8051261.html）

 1 #include <stdio.h>
 2 #include <queue>
 3 
 4 using namespace std;
 5 
 6 const int _N = 12000;
 7 const int INF = 1e9;
 8 
 9 struct edge {
10     int v, w;
11     edge(int v, int w):
12         v(v), w(w) { }
13 };
14 
15 vector<edge> G[_N];
16 int N, M;
17 int dis[_N], cnt[_N];
18 bool mk[_N];
19 deque<int> Q;
20 
21 bool SPFA(int p)
22 {
23     bool flag = false;
24     mk[p] = true;
25     for (int i = G[p].size()-1; i >= 0; --i) {
26         edge v = G[p][i];
27         if (dis[v.v] > dis[p]+v.w) {
28             dis[v.v] = dis[p]+v.w;
29             if (!mk[v.v]) {
30                 if (SPFA(v.v)) { flag = true; break; }
31             } else {
32                 flag = true;
33                 break;
34             }
35         }
36     }
37     mk[p] = false;
38     return flag;
39 }
40 
41 void Ins(int t0, int t1, int t2) { G[t0].push_back(edge(t1, t2)); return; }
42 
43 int main()
44 {
45     int i;
46     scanf("%d%d", &N, &M);
47     for (i = 1; i <= M; ++i) {
48         int a, b, c, ins;
49         scanf("%d%d%d", &ins, &a, &b);
50         if (ins == 1)
51             scanf("%d", &c), Ins(b, a, c);
52         else if (ins == 2)
53             scanf("%d", &c), Ins(a, b, -c);
54         else
55             Ins(a, b, 0), Ins(b, a, 0);
56     }
57     for (i = 1; i <= N; ++i)
58         if (SPFA(i)) break;
59     if (i != N+1) printf("No
");
60     else printf("Yes
");
61     return 0;
62 }

View Code