loj10093 网络协议
2024-08-29 10:38:55
分析
第一问我们不难想出是缩点之后的新图中入度为0的点的个数,对于第二问,我们画一画可以发现最优策略就是对于每一个入度为0的点都有一个出度为0的点连向它,而对于每一个出度为0的点也一定连向一个入度为0的点。所以最终答案即为出度为0的点和入度为0的点的最大值。注意特判缩点后只有一个点的情况。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
vector<int>v[];
int dfn[],low[],ist[],belong[],id[],od[],sum,cnt;
stack<int>a;
inline void tarjan(int x){
dfn[x]=low[x]=++cnt;
a.push(x);
ist[x]=;
for(int i=;i<v[x].size();i++)
if(!dfn[v[x][i]]){
tarjan(v[x][i]);
low[x]=min(low[x],low[v[x][i]]);
}else if(ist[v[x][i]]){
low[x]=min(low[x],dfn[v[x][i]]);
}
if(dfn[x]==low[x]){
sum++;
while(){
int u=a.top();
a.pop();
ist[u]=;
belong[u]=sum;
if(u==x)break;
}
}
return;
}
int main(){
int n,m,i,j,k,ans=,ans2=,tot=;
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%d",&m);
while(m){v[i].push_back(m);scanf("%d",&m);}
}
for(i=;i<=n;i++)
if(!dfn[i])tarjan(i);
for(i=;i<=n;i++)
for(j=;j<v[i].size();j++)
if(belong[i]!=belong[v[i][j]])
id[belong[v[i][j]]]++,od[belong[i]]++;
for(i=;i<=sum;i++){
if(!id[i])ans++;
if(!od[i])ans2++;
}
tot=max(ans,ans2);
if(sum==)tot=;
printf("%d\n%d\n",ans,tot);
return ;
}
最新文章
- WPF入门:XAML
- JS组件系列——图片切换特效:简易抽奖系统
- W3C代码标准规范
- 使用imap协议接收邮件
- C++ Primer 变量和基本类型
- Excel大数据量分段导入到Oracle
- php substr中文乱码最有效到解决办法 转:http://blog.sina.com.cn/s/blog_49b531af0100esah.html
- ARC指南2 - ARC的开启和禁止
- Hadoop Balance
- JSON反序列化实体类
- ( ̄y▽ ̄)~ 智能手机II
- linux 更换yum源
- 【Kafka源码】KafkaController启动过程
- Java笔记:语法基础
- python 爬取B站视频弹幕信息
- C#生成JOSN字符串
- 错误: Error creating bean with name &#39;studentController&#39;: Unsatisfied dependency expressed through field &#39;studentServiceImpl&#39;;
- python简明教程代码
- 从 Aliyun 经典网络迁移到 Aliyun VPC 网络
- Nginx配置笔记