首页 > 代码库 > BZOJ 4562 食物链
BZOJ 4562 食物链
我们需要拓扑一下。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #define maxv 100500 #define maxe 200500 using namespace std; int n,m,x,y,g[maxv],nume=1,d[maxv],size[maxv],ans=0; queue <int> q; bool flag[maxv]; struct pnt { int id,rank; }p[maxv]; struct edge { int v,nxt; }e[maxe]; bool cmp(pnt x,pnt y){return x.rank<y.rank;} void addedge(int u,int v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } void topusort() { for (int i=1;i<=n;i++) { if (!d[i]) { p[i].rank=1; q.push(i); } } while (!q.empty()) { int head=q.front();q.pop(); for (int i=g[head];i;i=e[i].nxt) { int v=e[i].v; if (!--d[v]) { p[v].rank=p[head].rank+1; q.push(v); } } } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); addedge(x,y);d[y]++; } for (int i=1;i<=n;i++) p[i].id=i; topusort(); sort(p+1,p+n+1,cmp); for (int i=n;i>=1;i--) { int x=p[i].id; for (int j=g[x];j;j=e[j].nxt) { int v=e[j].v; flag[x]=true;size[x]+=size[v]; } if (!flag[x]) size[x]=1; } for (int i=1;i<=n;i++) { if ((p[i].rank==1) && (flag[p[i].id])) ans+=size[p[i].id]; else if (p[i].rank!=1) break; } printf("%d\n",ans); return 0; }
BZOJ 4562 食物链
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。