一个很神奇的问题
查看原帖
一个很神奇的问题
120911
Lynkcat楼主2020/9/15 22:48

这是一份 6060 分的代码

//QwQcOrZ yyds!!!
#include<bits/stdc++.h>
#define N 105
#define int long long

using namespace std;

inline int read(){
    int x = 0; char ch = getchar(); bool positive = 1;
    for (; !isdigit(ch); ch = getchar())	if (ch == '-')	positive = 0;
    for (; isdigit(ch); ch = getchar())	x = x * 10 + ch - '0';
    return positive ? x : -x;
}
inline void write(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writesp(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
    printf(" ");
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
    }
    write(a); puts("");
}

int dp[N][5000],now,K,top,tim,n,m,w[N],v[N],d[N],flo[N],vis[N],zhan[N],dfn[N],low[N],ru[N],W[N],Val[N],ans;

vector<int>V[N],V1[N];

queue<int>q;

void tarjan(int k,int fa)
{
	//cout<<k<<endl;
    dfn[k]=low[k]=++tim;
    zhan[++top]=k;
    vis[k]=1;
    for (int i=0;i<V[k].size();i++)
      if (V[k][i]!=fa)
      {
      	if (!dfn[V[k][i]])
      	{
      		tarjan(V[k][i],k);
      		low[k]=min(low[k],low[V[k][i]]);
      	} else 
		if (vis[V[k][i]]) low[k]=min(low[k],dfn[V[k][i]]);
      }
    if (dfn[k]==low[k])
    {
    	K++;
    	do
    	{
    		now=zhan[top];
    		vis[now]=0;
    		flo[now]=K;
    		W[K]+=w[now];
    		Val[K]+=v[now];
    		top--;
    	} while (now!=k);
    }
}

void dfs(int k,int fa)
{
	//cout<<k<<" "<<fa<<endl;
	for (int i=W[k];i<=m;i++)
	  dp[k][i]=Val[k];
    for (int i=0;i<V1[k].size();i++)
    {
    	dfs(V1[k][i],k);
    	for (int j=m-W[k];j>=0;j--)
    	  for (int j1=0;j1<=j;j1++)
    	    dp[k][j+W[k]]=max(dp[k][j+W[k]],dp[V1[k][i]][j1]+dp[k][j+W[k]-j1]);
    }
}

signed main()
{
	n=read(),m=read();
	for (int i=1;i<=n;i++) w[i]=read();
	for (int i=1;i<=n;i++) v[i]=read();
	for (int i=1;i<=n;i++) 
	{
	    d[i]=read();
	    if (d[i]) V[d[i]].push_back(i);
	}
	for (int i=1;i<=n;i++)
	  if (!dfn[i])
	    tarjan(i,0);
	for (int i=1;i<=n;i++)
	{
	  if (flo[d[i]]!=flo[i]&&d[i]!=0)
	    V1[flo[d[i]]].push_back(flo[i]),ru[flo[i]]++;
    }
	for (int i=1;i<=K;i++)
	  if (ru[i]==0) ru[i]++,V1[K+1].push_back(i);
	dfs(K+1,0);
	writeln(dp[K+1][m]);	  
	//writeln(K);
}

然而我把 if (V[k][i]!=fa) 去掉就 A 了???

为什么啊我明明 fafa 写的是 00 啊,,

2020/9/15 22:48
加载中...