首页 > 代码库 > 10.10 review
10.10 review
Problem 1. Tree
Input file: tree.in
Output file: tree.out
Time limit: 1 second
给出 N 个点的树和 K，问能否把树划分成 N /K 个连通块，且每个连通块的点数都是 K。
Input
第 1 行，1 个整数 T ，表示数据组数。接下来 T 组数据，对于每组数据：
第 1 行，2 个整数 N, K。
接下来 (N − 1) 行，每行 2 个整数 Ai , Bi ，表示边 (Ai , Bi ）。点用 1, 2, . . . , N 编号。
Output
对于每组数据，输出 YES或 NO。
题解：这个题很水，只是当时没想到而已！~~~
实际上我们把整棵树划分出来仅需要暴搜就好了~~~2333
我们从叶子节点向上回溯，叶子节点是1，其父亲的值就是各子节点的和，以此类推，回溯上去，一旦超过k显然就是无解了~等于k的话我们就归零重新计数。
代码：by nevermore
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define MAXN 100100 6 struct Link 7 { 8 int to, next; 9 }l[MAXN * 2];10 int first[MAXN];11 int add = 0;12 void add_edge(int u, int v)13 {14 l[add].to = v;15 l[add].next = first[u];16 first[u] = add ++;17 }18 int T, n, k;19 int num[MAXN];20 int temp = 0;21 bool use[MAXN];22 bool dfs(int x)23 {24 use[x] = 1;25 for (int i = first[x]; ~ i; i = l[i].next)26 {27 if (!use[l[i].to])28 {29 if (dfs(l[i].to))30 num[x] += num[l[i].to];31 else return false;32 }33 }34 if (num[x] == k) num[x] -= k;35 else if (num[x] > k) return false;36 return true;37 }38 int main()39 {40 freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout);41 scanf("%d", &T);42 while (T --)43 {44 memset(use, 0, sizeof(use));45 add = 0;46 scanf("%d%d", &n, &k);47 int u, v;48 memset(first, -1, sizeof(first));49 for (int i = 1; i < n; i ++)50 {51 scanf("%d%d", &u, &v);52 add_edge(u, v);53 add_edge(v, u);54 }55 for (int i = 1; i <= n; i ++) num[i] = 1;56 if (dfs(1) && n % k == 0) printf("YES\n");57 else printf("NO\n");58 for (int i = 0; i < add; i ++)59 l[i].to = l[i].next = 0;60 }61 return 0;62 }
Problem 2. Graph
给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
Input
第 1 行，2 个整数 N, M 。
接下来 M 行，每行 2 个整数 Ui, Vi ，表示边 ?Ui, Vi?。点用 1, 2, . . . , N 编号。
Output
N 个整数 A(1), A(2), . . . , A(N )。
1 #include <queue> 2 3 #include <cstdio> 4 5 #include <cstring> 6 7 #include <algorithm> 8 9 using namespace std; 10 11 12 13 14 #define MAXN 100100 15 16 17 18 19 struct Link 20 21 { 22 23 int to, next; 24 25 }l[MAXN]; 26 27 int first[MAXN]; 28 29 30 31 32 int add = 0; 33 34 void add_edge(int u, int v) 35 36 { 37 38 l[add].to = v; 39 40 l[add].next = first[u]; 41 42 first[u] = add ++; 43 44 } 45 46 47 48 49 int n, m; 50 51 int ans[MAXN]; 52 53 54 55 56 queue <int> q; 57 58 bool use[MAXN]; 59 60 61 62 63 void bfs(int s) 64 65 { 66 67 q.push(s); 68 69 use[s] = 1; 70 71 while (!q.empty()) 72 73 { 74 75 int x = q.front(); 76 77 q.pop(); 78 79 for (int i = first[x]; ~ i; i = l[i].next) 80 81 if (!use[l[i].to]) 82 83 { 84 85 ans[l[i].to] = max(ans[l[i].to], ans[x]); 86 87 use[l[i].to] = 1; 88 89 q.push(l[i].to); 90 91 } 92 93 } 94 95 } 96 97 98 99 100 int main()101 102 {103 104 freopen("graph.in", "r", stdin);105 106 freopen("graph.out", "w", stdout);107 108 scanf("%d%d", &n, &m);109 110 int u, v;111 112 memset(first, -1, sizeof(first));113 114 for (int i = 1; i <= m; i ++)115 116 {117 118 scanf("%d%d", &u, &v);119 120 add_edge(v, u);121 122 }123 124 for (int i = 1; i <= n; i ++) ans[i] = i;125 126 for (int i = n; i >= 1; i --)127 128 if (ans[i] == i)129 130 bfs(i);131 132 for (int i = 1; i <= n; i ++)133 134 printf("%d ", ans[i]);135 136 return 0;137 }
in fact 我自己的思路和这个一点都不一样，我自己的思想是借鉴的最短路算法，我们每次只需要计原来的总边权为路径上最大的编号，三角不等式更新的时候只需要取max记好了。
唉（此处是二声）~这些好像我都写过。。。。。2333具体代码参见之前的随笔“最大路”，改改，那里是最大的边的权值，改成标号就好了~~更简单了不是么？
第三题必有蹊跷。。。。
10.10 review