第十一次CCF-CSP（第二题公共钥匙盒、第四题通信网络）

本文主要是介绍第十一次CCF-CSP（第二题公共钥匙盒、第四题通信网络），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第十一次CCF-CSP

第二题公共钥匙盒

原题链接：3248. 公共钥匙盒 - AcWing题库

思路分析

本来我想的是，先不让老师还钥匙，最后一块还。但是很显然这样是不对的。比如：当t=5时刻，钥匙3被还回来，t=6时刻，再次被借走。这种情况下，我的思路就是错的了…

下面说一下正确的思路：

由于既要考虑钥匙被借出去的时刻，又要考虑还回来的时刻。我们不妨建立一个结构体：

struct node
{int a, b;
};	//a 表示钥匙的序号，b 表示钥匙借出去/还回来的时刻
node key1[N], key2[N];	//key1[]表示借出钥匙，key2[]表示还回钥匙

这样一来，我们分别按照时间顺序对key1[] key2[] 进行排序，具体规则如下：

bool cmp(node& x, node& y)
{if (x.b == y.b)return x.a < y.a;return x.b < y.b;
}

然后利用双指针的思想，分别从前往后遍历key1[] 和 key2[] ，且 还钥匙的优先级要高于取走钥匙。

代码

#include<bits/stdc++.h>using namespace std;
const int N = 1010;
int n, m;
struct node
{int a, b;
};
node key1[N], key2[N];
int q[N];bool cmp(node& x, node& y)
{if (x.b == y.b)return x.a < y.a;return x.b < y.b;
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)q[i] = i;int a, b, c;for (int i = 1; i <= m; i++){cin >> a >> b >> c;key1[i] = { a,b };	//存放钥匙的序号 和拿走钥匙的时间点key2[i] = { a,b + c };	//存放钥匙的序号 和归还钥匙的时间点}sort(key1 + 1, key1 + 1 + m, cmp);sort(key2 + 1, key2 + 1 + m, cmp);int i=1, j=1;while (i <= m && j <= m){if (key1[i].b < key2[j].b)	//拿走钥匙的时间早于归还的时间 就先拿走{for (int k = 1; k <= n; k++)if (q[k] == key1[i].a){q[k] = 0;break;}i++;}else if (key1[i].b >= key2[j].b)	//当归还时间在前面时，要首先归还{for (int k = 1; k <= n; k++){if (q[k] == 0){q[k] = key2[j].a;break;}}j++;}}while (j <= m){for (int k = 1; k <= n; k++){if (q[k] == 0){q[k] = key2[j].a;// cout<<k<<" ";break;}}
// 		cout<<key2[j].a<<endl;j++;}for (int i = 1; i <= n; i++){cout << q[i] << " ";}return 0;
}

第四题通信网络

原题链接：3250. 通信网络 - AcWing题库

思路分析

题目的意思就是说，有一个有向图，它有 n 个节点， m条边。要求我们统计符合这样一个条件的节点的个数——从该点出发所能访问的点的个数加上从其他点出发能到达该点的个数 的和，恰好是 n 个节点。

既然是有向边，那么前者——该点出发所能访问的点的个数，直接搜索即可。

对于后者——从其他点出发能到达该点的个数，应该如何计算呢？

我们只需要从该点出发，逆向搜索！

为了满足我们逆向搜索的目的，就需要我们在建图的时候同时建立一个反向边！但是这样的话，有向边不就变成了无向边了吗？显然这样也是不合理的。

所以我们不妨建立两个图。其中一个存放正向边，另一个存放反向边！

下面看代码：

代码

#include<bits/stdc++.h>using namespace std;
const int N =1010,M=20010;
int h1[N],h2[N],e[M],ne[M],idx;
int n,m;
bool st1[N],st2[N];void add(int h[],int a,int b)
{e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}void dfs(int x,int h[],bool st[])
{st[x]=1;for(int i = h[x];~i;i=ne[i]){int j = e[i];if(!st[j])dfs(j,h,st);}
}int main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m;memset(h1,-1,sizeof h1);memset(h2,-1,sizeof h2);for(int i = 1;i<=m;i++){int a,b;cin>>a>>b;add(h1,a,b);add(h2,b,a);}int ans=0;for(int i = 1;i<=n;i++){memset(st1,0,sizeof st1);memset(st2,0,sizeof st2);dfs(i,h1,st1);dfs(i,h2,st2);int s = 0;for(int j = 1;j<=n;j++)	//这里表示，以节点 i 为起点进行dfs，从i点能到达的点（正向和反向）是否等于n个节点。{if(st1[j] || st2[j]){s++;}}if(s == n)ans++;}cout<<ans;return 0;
}