NJUCSE17

问题求解三 机试 非官方题解

2019-01-11 by Fancy

OJ 题意全靠猜。
数据范围全靠猜。
重边自环全靠猜。
有向无向全靠猜。
输入结束全靠猜。
错别字意全靠猜。
那要不要猜一猜考试成绩呢。

Problem A

判断输入 parent-child 关系是否构成一棵树。要求使用并查集。

搜到了原题。算法是：

Step 1：对每对输入的根节点标记表示这些节点出现过，进行并操作。并操作时两个节点不能有相同的根节点否则将构成环；假设b节点要接到a上，则要保证b节点是一个根节点，否则若进行并操作，b将会有两个父节点；若无以上情况，则可以合并两棵树。
Step 2：每组数据输入结束后，要计算整个图中的根节点总数，若根节点总数不为1，则构成的图不是一棵树。
Step 3：根据以上判断就可以输出结果了，每组结果输出后要初始化数据。

无法理解为什么要用并查集，明明找个入度为 0 的点搜索一下就 O(n) 了。
而且这个解法无法处理重边，题面也没说有没有重边自环，否则也不应该出现编号为 0 的点。
　
代码请看上面原题链接。

Problem B

给一个无向图，问是否存在从 Alice 家到 Bob 家再到学校的结点不重复的路径。

每个点拆点，流量为 1。源点流向 Bob 家，流量为 2。Alice 家和学校流向汇点，流量为 1。

判断最大流是否为 2。

现场默写 dinic，居然写对了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
const int N = 420, M = N * N * 2;
int n, m, ecnt, ds[N], head[N], S, T;
std::queue<int> Q;
struct edge {
  int to, rest, next;
} E[M];
void Addedge(int x, int y, int r) {
  E[++ecnt] = (edge) {y, r, head[x]};
  head[x] = ecnt;
  E[++ecnt] = (edge) {x, 0, head[y]};
  head[y] = ecnt;
}
int Bfs() {
  memset(ds, 0, sizeof(ds));
  ds[S] = 1;
  Q.push(S);
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (int e = head[x]; e; e = E[e].next) {
      int y = E[e].to;
      if (E[e].rest && !ds[y]) {
        ds[y] = ds[x] + 1;
        Q.push(y);
      }
    }
  }
  return ds[T];
}
int Dfs(int x, int flow) {
  if (x == T) return flow;
  int a = 0;
  for (int e = head[x]; e; e = E[e].next) {
    int y = E[e].to;
    if (E[e].rest && ds[y] == ds[x] + 1) {
      int b = Dfs(y, std::min(flow - a, E[e].rest));
      E[e].rest -= b;
      E[e ^ 1].rest += b;
      a += b;
      if (a == flow) break;
    }
  }
  if (!a) ds[S] = 0;
  return a;
}
int Dinic() {
  int ans = 0;
  while (Bfs()) ans += Dfs(S, 0x7fffffff);
  return ans;
}
int main() {
  int cas;
  for (scanf("%d", &cas); cas; --cas) {
    scanf("%d%d", &n, &m);
    S = 0;
    T = n * 2 + 1;
    ecnt = 1;
    memset(head, 0, sizeof(head));
    int x, y, z;
    for (int i = 1; i <= n; ++i)
      Addedge(i, i + n, 1);
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d", &x, &y);
      Addedge(n + x + 1, y + 1, 1);
      Addedge(n + y + 1, x + 1, 1);
    }
    scanf("%d%d%d", &x, &y, &z);
    Addedge(S, n + y + 1, 2);
    Addedge(n + x + 1, T, 1);
    Addedge(n + z + 1, T, 1);
    if (Dinic() == 2) printf("Yes\n");
    else printf("No\n");
  }
}

Problem C

给一棵树，每个点有一个权值，若选择一个点则其 parent 不能被选，问权值和最大的方案。

树形 DP，dp[i][0/1] 表示点 i 是否被选时子树的最大值。转移方程：
$dp[i][0]=\sum\limits_{child\ j}\max(dp[j][0],dp[j][1]),$

$dp[i][1]=value[i] + \sum\limits_{child\ j}dp[j][0].$

出题人又不知道树的边数是 n-1 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cassert>
#include <cstdio>
const int N = 6010;
int n, ecnt, root, a[N], du[N], dp[N][2], head[N];
struct edge {
  int to, next;
} E[N];
void Addedge(int x, int y) {
  E[++ecnt] = (edge) {y, head[x]};
  head[x] = ecnt;
}
void Dfs(int x, int pa) {
  dp[x][0] = 0;
  dp[x][1] = a[x];
  for (int e = head[x]; e; e = E[e].next) {
    int y = E[e].to;
    if (y == pa) continue;
    Dfs(y, x);
    dp[x][0] += std::max(dp[y][0], dp[y][1]);
    dp[x][1] += dp[y][0];
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
  for (int i = 1, x, y; i < n; ++i) {
    scanf("%d%d", &x, &y);
    du[x]++;
    Addedge(y, x);
  }
  for (int i = 1; i <= n; ++i) {
    if (du[i] == 0) {
      assert(root == 0);
      root = i;
    }
  }
  Dfs(root, 0);
  printf("%d\n", std::max(dp[root][0], dp[root][1]));
}

Problem D

给一个无向图，其中一些点为起点，一些为终点。问任意一对起点终点直接的最短距离。要求使用 Dijkstra。

源点和起点之间连边，代价为 0；终点和汇点之间连边，代价为 0。求 S 到 T 的最短路。
或者只建源点，终点判断一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
#include <utility>
#include <cstdio>
#include <queue>
const int N = 1005, M = 40010;
const int inf = 0x7fffffff;
struct edge {
  int to, cost, next;
} E[M];
int ecnt, n, S, head[N], ds[N];
std::priority_queue<std::pair<int, int> > q;
void Addedge(int x, int y, int z) {
  E[++ecnt] = (edge) {y, z, head[x]};
  head[x] = ecnt;
}
void Dijkstra() {
  for (int i = 0; i <= n; ++i) ds[i] = inf;
  q.push(std::make_pair(0, S));
  while (!q.empty()) {
    std::pair<int, int> x = q.top();
    q.pop();
    if (ds[x.second] < inf) continue;
    ds[x.second] = -x.first;
    for (int e = head[x.second]; e; e = E[e].next) {
      q.push(std::make_pair(x.first - E[e].cost, E[e].to));
    }
  }
}
int main() {
  int m, n1, n2;
  while (scanf("%d%d%d", &m, &n1, &n2) != EOF) {
    n = 1000;
    S = 0;
    ecnt = 0;
    memset(head, 0, sizeof(head));
    for (int i = 1, x, y, z; i <= m; ++i) {
      scanf("%d%d%d", &x, &y, &z);
      Addedge(x, y, z);
      Addedge(y, x, z);
    }
    for (int i = 1, x; i <= n1; ++i) {
      scanf("%d", &x);
      Addedge(S, x, 0);
    }
    Dijkstra();
    int ans = inf;
    for (int i = 1, x; i <= n2; ++i) {
      scanf("%d", &x);
      ans = std::min(ans, ds[x]);
    }
    printf("%d\n", ans);
  }
}
Tags: 编程
← 班级活动参加队列 “知名教授进支部”主题团日总结报告 →