hihoCoder hiho一下 第四十八周 题目1 : 拓扑排序·二

题意:

  给定一个拓扑图,其中部分结点含有1个病毒,每个结点只要收到病毒就会立即往出边所能到达的点传播,病毒数可叠加,求所有结点的病毒数总和。

思路:

  根据拓扑的特点,每个入度为0的点肯定不会再被传播病毒,而且会将自己的所有病毒向与其相连的结点传播。那么可以从入度味为0的点着手,逐个删除入度为0的结点,在删除的过程中,更新与其相连的结点的病毒数(即将病毒数累加到该结点),到最后所有结点都没了,各个结点所累积的病毒数的和就是答案。

 #include<bits/stdc++.h>
using namespace std;
const int N=;
const int mod=; bool init[N]; //初始是否有病毒
int cnt[N]; //各点的入度
vector< vector<int> > vect; //邻接表
int ans[N]; //各个节点的病毒数,不包括其自身初始的那个病毒 int cal(int n, int k)
{
vector<int> a;
for(int i=; i<=n; i++) if(!cnt[i]) a.push_back(i); //先装进去初始时入度为0的点 vector<int> b;
while(!a.empty())
{
b.clear();
for(int i=; i<a.size(); i++) //对于每个入度为0的点,更新与其相连的每个点的病毒数
{
for(int j=; j<vect[a[i]].size(); j++)
{
int tmp=vect[a[i]][j];
cnt[tmp]--; //入度减少1
ans[tmp]=(ans[tmp]+ans[a[i]]+init[a[i]])%mod; //更新病毒数,包括初始那个病毒
if(!cnt[tmp]) b.push_back(tmp); //又一个入度为0的
}
}
a.clear();
if(!b.empty())
a.insert(a.end(), b.begin(), b.end());
}
int sum=;
for(int i=; i<=n; i++) //统计
sum=(sum+ans[i])%mod;
sum+=k; //还有初始的病毒
return sum%mod;
} int main()
{
//freopen("e://input.txt","r",stdin);
int k, n, m, a, b;
cin>>n>>m>>k;
vector<int> tmp;
for(int i=; i<=n; i++) vect.push_back(tmp); //初始化 for(int i=; i<k; i++) //k个病毒
{
scanf("%d",&a);
init[a]=true;
}
for(int i=; i<m; i++) //m个边
{
scanf("%d%d",&a,&b);
vect[a].push_back(b);
cnt[b]++; //入度数
}
printf("%d\n",cal(n,k));
return ;
}

AC代码

上一篇:Asp.net Json数据解析的一种思路


下一篇:(spring-第13回【IoC基础篇】)PropertyEditor(属性编辑器)--实例化Bean的第五大利器