LibreOJ #10093. 「一本通 3.5 练习 1」网络协议&Luogu P2746校园网Network of Schools P2812校园网络【Network of Schools加强版】
LibreOJ #10093. 「一本通 3.5 练习 1」网络协议
Luogu P2746 [USACO5.3]校园网Network of Schools
Luogu P2812 校园网络【[USACO]Network of Schools加强版】
关于强连通分量，请见上一篇题解
传送门
题目、题解和代码
/*【题目描述】
出自 IOI 1996
一些学校连接在一个计算机网络上。学校之间存在软件支援协议。每个学校都有它应支援的学校名单（学校 a 支援学校 b，并不表示学校 b 一定支援学校 a）。当某校获得一个新软件时，无论是直接得到还是网络得到，该校都应立即将这个软件通过网络传送给它应支援的学校。因此，一个新软件若想让所有连接在网络上的学校都能使用，只需将其提供给一些学校即可。
任务
请编一个程序，根据学校间支援协议（各个学校的支援名单），计算最少需要将一个新软件直接提供给多少个学校，才能使软件通过网络被传送到所有学校；
如果允许在原有支援协议上添加新的支援关系。则总可以形成一个新的协议，使得此时只需将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件。编程计算最少需要添加几条新的支援关系。
【输入】
第一行是一个正整数 n，表示与网络连接的学校总数。 随后 n 行分别表示每个学校要支援的学校，即：i+1 行表示第 i 号学校要支援的所有学校代号，最后 0 结束。
如果一个学校不支援任何其他学校，相应行则会有一个 0。一行中若有多个数字，数字之间以一个空格分隔。
【输出】
包含两行，第一行是一个正整数，表示任务 a 的解，第二行也是一个正整数，表示任务 b 的解。
【输入样例】
5
2 4 3 0
4 5 0
0
0
1 0
【输出样例】
1
2
【提示】
数据范围与提示:
2≤n≤100。
（Luogu P2812，题意相同，数据范围为5000000）
由于这题思路同上题完全相同，不再赘述。
不同点：求最少加几条边，使得整个图变成一个强连通分量。
如果整个图就是一个强连通分量，答案为0（需特判）。
否则，答案为max(入度为0的点的个数,出度为0的点的个数)*/
#include<iostream>
#include<vector>
using namespace std;
template<typename t>
inline int min(t& a,t& b)
{
return a<b?a:b;
}
/* template<typename _Tp, typename _Compare>
inline const _Tp&
max(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
//return __comp(__a, __b) ? __b : __a;
if (__comp(__a, __b))
return __b;
return __a;
}((vector内)忘了写max代码，就从源文件中摘抄出来了)*/
vector<int>edge[5000001];
int dfn[5000001],low[5000001],sta[5000001],ty[5000001],idu[5000001],odu[5000001],num,top,typ,ans1,ans2;//ans1代表入度为0的点个数，ans2代表出度为0的点个数，idu为入度，odu为出度，其他详见前一篇题解
inline void tarjan(int x)//不解释
{
dfn[x]=low[x]=++num;
sta[++top]=x;
for(register vector<int>::iterator i=edge[x].begin();i!=edge[x].end();++i)
{
register int y=*i;
if(dfn[y])
{
if(!ty[y])
{
low[x]=min(low[x],dfn[y]);
}
}
else
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
}
if(low[x]==dfn[x])
{
ty[x]=++typ;
while(sta[top]!=x)
{
ty[sta[top]]=typ;
--top;
}
--top;
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
register int n,a;
cin>>n;
for(register int i=1;i<=n;++i)
{
cin>>a;
while(a)//读入数不为0
{
edge[i].push_back(a);
cin>>a;
}
}
for(register int i=1;i<=n;++i)
{
if(!dfn[i])
{
tarjan(i);//搜索
}
}
for(register int i=1;i<=n;++i)
{
for(register vector<int>::iterator j=edge[i].begin();j!=edge[i].end();++j)
{
int x=*j;
if(ty[i]!=ty[x])
{
++idu[ty[x]];//入度加1
++odu[ty[i]];//出度加1
}
}
}
for(register int i=1;i<=typ;++i)
{
if(!idu[i])//入度为0
{
++ans1;
}
if(!odu[i])//出度为0
{
++ans2;
}
}
cout<<ans1<<'\n'<<(typ==1?0:max(ans1,ans2));//如果只有1个强连通分量，第二个数为0
return 0;
}效率：
LibreOJ：（更改了数据范围为101，否则会MLE）
测试点 #1 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #2 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #3 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #4 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #5 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #6 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #7 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #8 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #9 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #10 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #11 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #12 Accepted 得分：100 用时：3 ms 内存：252 KiB
Luogu（USACO版）：（未更改数据范围）
用时: 2745ms / 内存: 118276KB
测试点信息
1
AC 248ms/118048KB
2
AC 253ms/118276KB
3
AC 248ms/118192KB
4
AC 249ms/118052KB
5
AC 247ms/118152KB
6
AC 257ms/118052KB
7
AC 244ms/118056KB
8
AC 251ms/118072KB
9
AC 245ms/118036KB
10
AC 254ms/118032KB
11
AC 249ms/118032KB
Luogu（加强版）：（很奇怪，竟然没有MLE，虽然118800KB=116.02MB）
用时: 2519ms / 内存: 118800KB
测试点信息
1
AC 249ms/117992KB
2
AC 261ms/118800KB
3
AC 249ms/118052KB
4
AC 249ms/118152KB
5
AC 251ms/117980KB
6
AC 252ms/118036KB
7
AC 249ms/118052KB
8
AC 251ms/118176KB
9
AC 253ms/118284KB
10
AC 255ms/118564KB