20分悬关QAQ
  • 板块P1113 杂务
  • 楼主H_dream
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/19 18:40
  • 上次更新2024/6/19 21:01:42
查看原帖
20分悬关QAQ
1180231
H_dream楼主2024/6/19 18:40
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10010,inf=1e18;
int n;
struct node{
	int len,cnt=0;
	vector<int> v;
}vt[N];
int bfs(){
	int ans=0;
	vector<int> q;
	for(int i=1;i<=n;++i){
		if(!vt[i].cnt) q.push_back(i);
	}
	while(!q.empty()){
		/*
		for(auto i:q){
			cout<<i<<' ';
		}
		cout<<endl;
		*/
		vector<int> p=q;
		int x=inf;
		for(auto i:p){
			x=min(vt[i].len,x);
		}
		//cout<<x<<endl;
		ans+=x;
		int tmp=0;
		for(int i=0;i<p.size();++i){
			vt[p[i]].len-=x;
			if(vt[p[i]].len<=0){
				//cout<<p[i]<<" Hi!"<<endl;
				q.erase(q.begin()+i+tmp++);
				for(auto j:vt[p[i]].v){
					vt[j].cnt--;
					if(vt[j].cnt==0) q.push_back(j);
				}
			}
		}
	}
	return ans;
}
signed main(){
    cin>>n;
    int m=n;
    while(m--){
        int i,t,j;
        cin>>i>>t;
        vt[i].len=t;
        while(cin>>j){
            if(!j) break;
            vt[j].v.push_back(i);
            vt[i].cnt++;
        }
    }
    /*
    for(int i=1;i<=n;++i){
        cout<<i<<" "<<vt[i].cnt<<endl<<" ";
        for(auto x:vt[i].v) cout<<x<<' ';
        cout<<endl;
    }
    */
    cout<<bfs();

	return 0;
}
2024/6/19 18:40
加载中...