django做的购物网站/推广普通话手抄报简单又好看内容

其实挺明显的一道题，我们画图可以发现对于一个图，我们不好观察，于是我们先缩成DAG。

然后只有入度为0的点不能取。

对于一个强连通分量，如果入度不为0，那么可以取完，否则必须剩下一个。

然后对能取的取k个最大的即可。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10;
int n,m,k,a[N],deg[N],res;
int low[N],dfn[N],scc[N],vis[N],co,cnt;
vector<int> g[N],v[N],p;	stack<int> s;
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){int x=0,f=1; char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}return x*f;
}
int cmp(int a,int b){return a>b;}
void Tarjan(int x){low[x]=dfn[x]=++cnt;	s.push(x),vis[x]=1;for(auto to:g[x]){if(!dfn[to])	Tarjan(to),low[x]=min(low[x],low[to]);else if(vis[to])	low[x]=min(low[x],dfn[to]);}if(low[x]==dfn[x]){int u;	co++;do{u=s.top(),s.pop(); scc[u]=co,vis[u]=0; v[co].push_back(a[u]);}while(u!=x);}
}
signed main(){n=read(),m=read(),k=read();for(int i=1;i<=n;i++)	a[i]=read();for(int i=1,x,y;i<=m;i++)	x=read(),y=read(),g[x].push_back(y);for(int i=1;i<=n;i++)	if(!dfn[i])	Tarjan(i);for(int i=1;i<=n;i++)	for(auto to:g[i])	if(scc[i]!=scc[to])	deg[scc[to]]++;for(int i=1;i<=co;i++){if(v[i].size()==1){if(deg[i])	p.push_back(v[i][0]);}else{sort(v[i].begin(),v[i].end());for(int j=(deg[i]==0?1:0);j<v[i].size();j++)	p.push_back(v[i][j]);}}sort(p.begin(),p.end(),cmp);for(int i=0;i<min(k,(int)p.size());i++)	res+=p[i];cout<<res;return 0;
}