标签：memset idx int 888 Codeforces long 补题 Div sizeof
本题的题面保证了本题是个无环图，允许dfs函数会有出口，存图不能用链式前向图，因为非常容易构造数据使得为稠密图，所以用二维数组或vector数组或二维vector（注意区别，这三者不是一个东西）来存。
debug历程：（本题难度稍微上升可以感觉到封装函数的重要性，全局变量开太多会导致每轮都需要还原一堆变量）
- 1.最重要的是递归函数一开写的不对，多考虑了一层，没有思考清楚dfs函数返回值的意义
- 2.没分析数据范围，存图方式不对
- 3.对于vector数组和二维vector混为一谈，导致clear的时候出错
- 4.学会了使用cerr错误流来调试
// Problem: E. Nastya and Potions
// Contest: Codeforces - Codeforces Round 888 (Div. 3)
// URL: https://codeforces.com/contest/1851/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
# define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int N = 2e5 + 10;
const int M = 4e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int n, m;
int a[N];
int f[N];
vector<int>e[N];
//int h[N],e[M],ne[M],idx;
// void add (int a,int b){
// e[idx]=b;
// ne[idx]=h[a];
// h[a]=idx++;
// }//稠密图不适合用邻接表
int dfs(int u){
int &v=f[u];
if(v!=-1)return v;
v=0;
for(int i=0;i<e[u].size();i++)v+=dfs(e[u][i]);
v=min(v,a[u]);
//cerr<<u<< " "<<v<<endl;
return v;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
cin>>t;
while (t--) {
memset(f,-1,sizeof f);
// memset(h,-1,sizeof h);
// memset(e,0,sizeof e);
// memset(ne,0,sizeof ne);
memset(a,0,sizeof a);
//idx=0;
cin>>n;
for(int i=1;i<=n;i++)e[i].clear();
int k;
cin>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=k;i++){
int x;
cin>>x;
f[x]=0;
}
for(int i=1;i<=n;i++){
int m;
cin>>m;
if(m==0&&f[i]==-1)f[i]=a[i];
while(m--){
int b;
cin>>b;
e[i].push_back(b);
}
}
for(int i=1;i<=n;i++)cout<<dfs(i)<<" ";
cout<<endl;
}
return 0;
}
标签：memset,
idx,
int,
888,
Codeforces,
long,
补题,
Div,
sizeof
From： https://www.cnblogs.com/mathiter/p/17594101.html