昨天 7月24日，我们智灵班去听了金牌讲师周镇东的课，讲的是超级难的省选图论
我先前是听的，结果一点也不会，后来电脑没电了，直接睡觉
我们敬爱的老师 @王建力 ，为了帮助我们重回清醒，给我们出了个图论基础的题单
由于这里图论搜索基础太过于简单，不在讲解，而是直接将题
题目非常简单，我之前做过，思路就是看一看图和树的区别，如果在树上找到一条边，图上没有存在，就输出 imppossible ，如果没找到输出 m-n+1
code
cin >> n >> m;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
vis[x][y] = 1;
vis[y][x] = 1;
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
vis2[x][y] = 1;
vis2[y][x] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (vis[i][j] && !vis2[i][j]) {
cout << "impossible\n";
return 0;
}
}
}
cout << m - n + 1 << endl;
真的好水，就是连通块问题，把已经遍历过的连通块标记一下即可
code
void dfs(int x) {
for(auto i : v[x]){
if(!vis[i]){
vis[i] = 1;
dfs(i);
}
}
}
for (int i = 1;i <= n;i++) {
if (!vis[i]) {
dfs(i);
res++;
}
}
水，直接把每头奶牛表上编号，遍历所有奶牛，如果走到了一个点，那个点的奶牛数量就++，随后看看，有几个点有n头奶牛，就答案++
code
void dfs(int x){
for (int i = 0; i < v[x].size(); i++) {
if (!vis[v[x][i]]) {
vis[v[x][i]] = true;
sum[v[x][i]]++;
dfs(v[x][i]);
}
}
}
for (int i = 1 ; i <= k ; i++) {
memset(vis, false, sizeof(vis));
vis[id[i]] = true;
dfs(id[i]);
}
int res = 0;
for (int i = 1 ; i <= n ; i++) {
if (sum[i] == k) res++;
// cout << sum[i] << endl;
}
不是很水，如果我们暴力在每一个点去搜索，会炸掉的，我们可以从编号最大的节点开始搜索，看看他能走到哪一个点，那个点的最大编号就是这个遍历到的点的编号
code
void dfs(int x, int sum) {
if (ans[x] == 0) ans[x] = sum;
for (int i = 0; i < v[x].size(); i++) {
int nx = v[x][i];
if (!ans[nx]) {
ans[nx] = sum;
dfs(nx, sum);
}
}
}
for (int i = n; i >= 1; i--) {
dfs(i, i);
}
水，暴力就可以过了，直接枚举每一个能放物资点的地方，每次走过一个运送物资的桥（简称物资桥），就把距离+1，随后用距离 \times 员工数量就是那个点所需的力量
code
void dfs(int x, int step) {
for (int i = 0; i < v[x].size(); i++) {
int nx = v[x][i];
if (!vis[nx]) {
vis[nx] = true;
sum += step * w[nx];
dfs(nx, step + 1);
vis[nx] = false;
}
}
}
for (int i = 1; i <= n; i++) {
sum = 0;
dfs(i, 0);
res = min(res, sum);
}
十分煎蛋
把联通块提出来（数量）即可
难就难在怎么统计数量，很明显我们要把两个联通块数量相乘加上，但枚举的时间就是 O(n^2) ，会超时，我们可以先把所有的点统计好，随后一直乘这个数量，每次减去上次用的（因为不会再用到）
code
void dfs(int x) {
vis[x] = true;
f[cnt]++;
for (int i = 0; i < v[x].size(); i++) {
int nx = v[x][i];
if (!vis[nx]) {
dfs(nx);
}
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
cnt++;
dfs(i);
}
}
ll res = 0;
ll ans = 0;
for (int i = 1; i <= n; i++) {
res += f[i];
}
for (int i = 1; i <= n; i++) {
res -= f[i - 1];
ans += res * f[i - 1];
}
其实直接随便dfs即可，每次开始就答案++
code
void dfs(int x) {
if (res >= M) return;
vis[x] = true;
res++;
for (int i = 0; i < v[x].size(); i++) {
if (!vis[v[x][i]]) {
dfs(v[x][i]);
}
}
vis[x] = false;
}
我不会，所以——
不可以！总司令！
code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 6) puts("3");
else puts("0");
return 0;
}
暴力，但也不是纯暴力，可以在2层与3层里枚举i认识的人，去min即可
code
for(long long i=1;i<=n;i++)for(long long j=0;j<a[i].size();j++)for(long long l=j+1;l<a[i].size();l++)if(b[a[i][j]][a[i][1]]==1)ans=min(ans,c[a[i][1]]+c[i]+c[a[i][j]]-6);
数学题，但我数学不好，不会讲
code
void init(){
int n,m;
cin>>n>>m;
int x,y,xy;
vector<int> c(n+1);
for(int i=0;i<m;i++)
{
cin>>x>>y;
x--;y--;
c[x]++;c[y]++;
}
xy=count(c.begin(),c.end(),1);
x=n-xy-1;
y=xy/x;
cout<<x<<" "<<y<<"\n";
}
很煎蛋
我们可以分析一下
- 菊花图，有 n-1 个点连着1条边，另一个点连着 n-1 条边
- 链条，有两个点连着1条边， n-2 个点连着2条边
- 环形，所有点都连着2条边
这样特别好做，不用说了，就是if、else的问题
code
for (int i = 1; i <= n; i++) {
if (v[i].size() == 1) {
a++;
}
if (v[i].size() == 2) {
b++;
}
if (v[i].size() == n - 1) {
c++;
}
}
if (a == n - 1 && c == 1) {
cout << "Flower";
} else if (b == n) {
cout << "Ring";
} else if (a == 2 && b == n - 2) {
cout << "Chain";
} else {
cout << "Neither";
}