题4：RC-u4 章鱼图的判断    分数 25

题目：

对于无向图 G=(V,E)，我们将有且只有一个环的、大于 2 个顶点的无向连通图称之为章鱼图，因为其形状像是一个环（身体）带着若干个树（触手），故得名。

给定一个无向图，请你判断是不是只有一个章鱼子图存在。

输入格式:
输入第一行是一个正整数 T (1≤T≤5)，表示数据的组数。

每组数据的第一行是两个正整数 N,M (1≤N,M≤10 
5
 )，表示给定的无向图有 N 个点，M 条边。

接下来的 M 行，每行给出一条边两个端点的顶点编号。注意：顶点编号从 1 开始，并且题目保证任何边不会重复给出，且没有自环。

输出格式:
对于每组数据，如果给定的图里只有一个章鱼子图，则在一行中输出 Yes 和章鱼子图环的大小（及环中顶点数），其间以 1 个空格分隔。

否则，则在一行中输出 No 和图中章鱼子图的个数，其间以 1 个空格分隔。

输入样例:

3
10 10
1 3
3 5
5 7
7 9
1 2
2 4
2 6
3 8
9 10
1 9
10 10
1 3
3 5
5 7
7 9
9 1
1 2
2 4
4 8
8 10
10 1
10 10
1 3
3 5
5 7
7 9
9 1
2 4
4 8
8 10
10 2
10 6

输出样例:

Yes 5
No 0
No 2

考点：

并查集、BFS

解题：

本题考查的是并查集和BFS，通过并查集的基本模板来判断是否存在环，不过本题需要注意的是一个点可能在多个环当中，因此我们需要记录一下每个存在的个数，其中只有一个记录时则可以统计这个是一个环，再利用BFS算法来进行从环的起始点到终点的长度。

代码：

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAXS = 1e5 + 5;
int f[MAXS], num[MAXS], Size[MAXS];
vector<int> cnt[MAXS];
int find(int x)
{if (f[x] != x) f[x] = find(f[x]);return f[x];
}
void solve()
{int N, M, start, end;cin >> N >> M;//初始化int huan = 0;for (int i = 1; i <= N; i++) {f[i] = i, cnt[i].clear(), num[i] = 0, Size[i] = -1;}while (M--){int a, b; cin >> a >> b;cnt[a].push_back(b);cnt[b].push_back(a);int f_a = find(a), f_b = find(b);if (f_a == f_b)//有环{num[f_a]++;start = a, end = b;}else{f[f_a] = f_b;num[f_b] += num[f_a];}}for (int i = 1; i <= N; i++)if (find(i) == i && num[i] == 1)huan++;if (huan != 1)//无环或者不止一个环{cout << "No " << huan << endl;}else{//BFSqueue<int> s;s.push(start);Size[start] = 1;while (!s.empty()){auto first = s.front(); s.pop();for (auto& second : cnt[first]){if (first == start && second == end) continue;if (Size[second] == -1){Size[second] = Size[first] + 1;s.push(second);}}}cout << "Yes " << Size[end] << endl;}}
int main()
{int T;cin >> T;while (T--){solve();}
}

题5：RC-u5 工作安排   分数 30

题目：

小 K 有 N 项工作等待完成，第 i 项工作需要花 ti单位时间，必须在 di时刻或之前完成，报酬为 pi。假设小 K 工作时刻从 0 开始，且同一时刻只能做一项工作、工作一旦开始则不可中断或切换至其他工作，请你帮小 K 规划一下如何选择合适的工作，使小 K 可以获得最多的报酬。

输入格式:
输入第一行是一个正整数 T (≤5)，表示数据的组数。

接下来有 T 组数据，每组数据第一行是一个正整数 N (≤5000)，表示待完成工作的数量。接下来的 N 行，每行三个非负整数 ti、di、pi(均 ≤5000；1≤i≤N)，表示第 i 项工作需要花费的时间、截止时间以及报酬。

输出格式:
对于每组数据，输出小 K 能获得最多的报酬是多少。

输入样例:

3
5
1 2 50
3 3 100
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 20
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 100
1 5 1
3 2 5000
5 5 800

输出样例:

101
80
800

考点：

01背包

解题：

本题主要考察的是01背包问题，将时间作为背包的容量，将完成的任务看作所占空间大小(t、d)和价值(p)，其中所占空间是一个弹性的范围【t—(d-t)】。其次，我们在执行dp的过程中如果d大的而p小的在前进行判断则会影响dp的进行，因此我们需要按照d从小到大的顺序进行排序。

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXS = 5005;
typedef struct Node {int t;int d;int p;
};
Node node;
vector<Node> cnt;
bool cmp(Node a, Node b) {return a.d < b.d;
}
long long int solve()
{long long int ans = 0;int N; cin >> N;cnt.clear(); long long int dp[MAXS] = { 0 };for (int i = 0; i < N; i++){cin >> node.t >> node.d >> node.p;cnt.push_back(node);}//sortsort(cnt.begin(), cnt.end(), cmp);//（t)-(d-t)的时间内for (auto& a : cnt){for (int i = a.d; i >= a.t; i--){dp[i] = max(dp[i], dp[i - a.t] + a.p);ans = max(ans, dp[i]);}}return ans;
}
int main()
{int T; cin >> T;while (T--){cout << solve() << endl;}return 0;
}