Kosaraju求强连通分量,AC#1#8#11,其它全WA,求调
查看原帖
Kosaraju求强连通分量,AC#1#8#11,其它全WA,求调
658620
Youth_Glory楼主2024/7/18 10:51
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

ll n,m,w,scc_cnt;
bool vis[10005];
vector<ll>edge[10005];
stack<ll>st;

struct clouds{
	ll money,value;
}cloud[10005];

struct sccs{
	ll money=0,values=0;
}scc[10005];

inline void dfs1(ll id){
	vis[id]=true;
	for(ll it : edge[id])if(!vis[it])dfs1(it);
	st.push(id);
}

inline void dfs2(ll id){
	vis[id]=true;
	scc[scc_cnt].money+=cloud[id].money;
	scc[scc_cnt].values+=cloud[id].value;
	for(ll it : edge[id])if(!vis[it])dfs2(it);
}

bool cmp(sccs a,sccs b){return a.values>b.values;}

signed main()
{
	IOS;
	cin>>n>>m>>w;
	for(ll i=1;i<=n;i++)cin>>cloud[i].money>>cloud[i].value;
	for(ll i=1,u,v;i<=m;i++){
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for(ll i=1;i<=n;i++)if(!vis[i])dfs1(i);
	memset(vis,false,sizeof vis);
	while(!st.empty()){
		if(!vis[st.top()]){
			++scc_cnt;
			dfs2(st.top());
		}
		st.pop();
	}
	sort(scc+1,scc+scc_cnt+1,cmp);
	for(ll i=1;i<=scc_cnt;i++){
		if(scc[i].money<=w){
			cout<<scc[i].values;
			return 0;
		}
	}
	cout<<0;
	return 0;
}
2024/7/18 10:51
加载中...