WHY TLE?
查看原帖
WHY TLE?
826079
Autumn_Rain楼主2024/4/15 16:47

RT。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5010,inf=0x3f3f3f3f;
int n,p,a,b,r;
int m[N];
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
    return x*f;
}
struct node{
	int nxt,to;
}e[N];
int h[N],cnt;
void add(int u,int v){
	e[++cnt].nxt=h[u];
	e[cnt].to=v;
	h[u]=cnt;
}
int indeg[N],money[N];
int dfn[N],low[N];
bool ins[N];
int tot,idx,st[N],top,bel[N]; 
void tarjan(int u){
	low[u]=dfn[u]=++tot;
	st[++top]=u;
	ins[u]=1;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		int v;
		++idx;
		do{
			money[idx]=min(money[idx],m[st[top]]);
			v=st[top--];
			bel[v]=idx;
			ins[v]=0;
		}while(v!=u);
	}
}
long long ans;
int main(){
	n=read();p=read();
	for(int i=1;i<=n;i++){
		m[i]=inf;
		money[i]=inf;
	} 
	while(p--){
		a=read();b=read(); 
		m[a]=b;
	}
	r=read(); 
	while(r--){
		a=read();b=read(); 
		add(a,b);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]&&m[i]!=inf)tarjan(i);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			printf("NO\n%d",i);
			return 0;
		}
	}
	printf("YES\n");
	for(int i=1;i<=n;i++){
		for(int j=h[i];j;j=e[i].nxt){
			if(bel[i]!=bel[e[j].to]){
				indeg[bel[e[j].to]]++;
			}
		}
	}
	for(int i=1;i<=idx;i++){
		if(!indeg[i]){
			ans+=money[i];
		}
	}
	printf("%lld",ans);
	return 0;
} 
2024/4/15 16:47
加载中...