我校神仙出的神仙题 \(\%\%\%\)
30分
找出所有有入度的点，排序，选前\(k\)个点，好了，30分到手。
#include#include #include #include #define LL long longusing namespace std;int read(){ int k=0,f=1; char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1; for(;c>='0'&&c<='9';c=getchar()) k=k*10+c-48; return k*f;}int a[100010],sum,in[100010],b[100010],top;bool cmp(int x,int y){ return x > y;}int main(){ int n=read(),m=read(),k=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(); in[y]++; } for(int i=1;i<=n;i++) if(in[i]) b[++top]=a[i]; sort(b+1,b+top+1,cmp); for(int i=1;i<=k;i++) sum+=b[i]; cout<
就这么简单
这个做法可以\(A\)掉\(DAG\)的\(Subtask\)
因为图是一个\(DAG\)，所以对于所有有入度的点，一定可以将它们全部删去——从后向前删即可。既然所有有入度的点都能删去，我们只要贪心的取出前\(k\)大就好了。AC
对于\(DAG\)，一定可以将所有有入度的点全部删去，而普通有向图就不一样了——有环的存在
如上面\(4\)个点，它们形成了一个环，我们最多只能删掉\(3\)个。因为必定会有一个点被留下，所以我们贪心的留下点权最小的点。 但对环的讨论是十分繁琐的，我们可以先将整张图用\(Tarjan\)缩成一张\(DAG\)，每个强连通分量内一定至少有一个环。对于强连通分量，我们分类讨论一下。 - 对于缩点后有入度的强连通分量，十分显然，它内部的点我们可以随便选
- 没有入度的强连通分量，我们必定要留下一个，理由如上所说。同理，我们贪心的留下点权最小的点即可。
#include#include #include #include using namespace std;int read(){ int k=0; char c=getchar(); for(;c<'0'||c>'9';) c=getchar(); for(;c>='0'&&c<='9';c=getchar()) k=k*10+c-48; return k;}struct zzz{ int f,t,nex;}e[2000010]; int head[500010],tot;void add(int x,int y){ e[++tot].t=y; e[tot].f=x; e[tot].nex=head[x]; head[x]=tot;}struct hhh{ int v,pos; }a[500010];int dfn[500010],low[500010],deep,vis[500010],colnum[500010],belong[500010],col,s[500010],top;void Tarjan(int now){ //Tarjan缩点 dfn[now]=low[now]=++deep; s[++top]=now; vis[now]=1; for(int i=head[now];i;i=e[i].nex){ if(!dfn[e[i].t]){ Tarjan(e[i].t); low[now]=min(low[now],low[e[i].t]); } else if(vis[e[i].t]) low[now]=min(low[now],dfn[e[i].t]); } if(dfn[now]==low[now]){ col++; int v=0; do{ v=s[top--]; vis[v]=0; colnum[col]++; belong[v]=col; }while(v!=now); }}int in[500010],ans;bool cmp(hhh x,hhh y){ return x.v < y.v;}bool cmp2(hhh x,hhh y){ return x.v > y.v;}bool flag[500010],mapp[500010];int main(){ int n=read(),m=read(),k=read(); for(int i=1;i<=n;i++) a[i].v=read(), a[i].pos=i; for(int i=1;i<=m;i++){ int x=read(),y=read(); add(x,y); } for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i); memset(head,0,sizeof(head)); for(int i=1;i<=tot;i++){ //缩点之后处理入度 if(belong[e[i].f]!=belong[e[i].t]) ++in[belong[e[i].t]]; } //=======剔除入度为0的强联通分量里点权最小的点 sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++){ if(!in[belong[a[i].pos]]&&!flag[belong[a[i].pos]]){ flag[belong[a[i].pos]]=1; mapp[a[i].pos]=1; } } int cnt=0; //=======贪心的从大到小选点 sort(a+1,a+n+1,cmp2); for(int i=1;i<=n;i++){ if(cnt==k) break; if(mapp[a[i].pos]) continue; ans+=a[i].v; cnt++; } cout<
在文章的最后,放一下，233~~~