Exchanging Gifts 【拓扑】
来源
https://codeforces.com/gym/102394/problem/E
思路
代码
拓扑排序
#include
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define sz(x) (x).size()
#define dd(x) cout<<#x<<'='<'9')){
c=getchar();
}
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9'){
ret=ret*10+(c-'0');
}
ret*=sgn;
return 1;
}
vector fa[1000010];
vector a[1000010];
ll kk[1000010],du[1000010];
unordered_map cnt;
ll maxx,sum;
void topo(ll st,ll n){
cnt.clear();
maxx=sum=0;
queue q;
for (int i=1; i<=n; i++)
if (du[i]==0) q.push(i);
kk[st]=1;
while (!q.empty()){
ll u=q.front();
q.pop();
if (fa[u].empty()){
for (ll i=0; isum-maxx) cout<<(sum-maxx)*2LL< 改进后
#include
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define sz(x) (x).size()
#define dd(x) cout<<#x<<'='<'9')){
c=getchar();
}
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9'){
ret=ret*10+(c-'0');
}
ret*=sgn;
return 1;
}
vector fa[1000010];
vector a[1000010];
ll kk[1000010],du[1000010];
map cnt;
ll maxx,sum;
int main(){
ll t;
read(t);
while (t--){
ll n;
read(n);
for (ll i=1; i<=n; i++){
ll op;
read(op);
if (op==1){
ll k;
read(k);
for (ll j=1; j<=k; j++){
ll qq;
read(qq);
a[i].pb(qq);
}
}
if (op==2){
ll x,y;
read(x);
read(y);
fa[i].pb(x);
fa[i].pb(y);
du[x]++;
du[y]++;
}
}
cnt.clear();
kk[n]=1;
maxx=sum=0;
for (int i=n; i>=1; i--){
if (fa[i].empty()){
for (int j=0; jsum-maxx) cout<<(sum-maxx)*2LL< 参考文献
[1] https://blog.csdn.net/weixin_42856843/article/details/104460891