题目传送门 https://www.luogu.org/problemnew/show/P1038
这道题目没有什么难的, 是一道拓扑排序 + 递推的题目. 我的思路是开始处理出拓扑序, 然后因为数据范围很小怎么搞都可以, 就邻接矩阵存图 + 暴力枚举. 结果 60 分.
后来看题解发现, 大家都是边拓扑边进行递推的, 才发现自己这部分可能不对. 另外的, 就都是一些细节了 ==.
Code
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- using namespace std;
- int n,m,tot,cnt;
- int c[500],head[500],cdu[500],rdu[500],seq[500];
- struct node{
- int to,val,next;
- }edge[20000];
- void add(int x,int y,int z)
- {
- edge[++tot].to=y;
- edge[tot].next=head[x];
- edge[tot].val=z;
- head[x]=tot;
- }
- void topo()
- {
- queue<int>q;
- for(int i=1;i<=n;i++)
- if(rdu[i]==0) q.push(i);
- while(!q.empty())
- {
- int x=q.front();q.pop();
- seq[++cnt]=x;
- for(int i=head[x];i;i=edge[i].next)
- {
- int y=edge[i].to;
- if(--rdu[y]==0) q.push(y);
- if(c[x]>0) c[y]+=edge[i].val*c[x];
- }
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- {
- int x=0;
- scanf("%d%d",&c[i],&x);
- if(c[i]==0) c[i]-=x;
- }
- for(int i=1;i<=m;i++)
- {
- int x=0,y=0,z=0;
- scanf("%d%d%d",&x,&y,&z);
- add(x,y,z);rdu[y]++;cdu[x]++;
- }
- topo();
- bool flag=0;
- for(int i=1;i<=n;i++)
- if(cdu[i]==0&&c[i]>0) printf("%d %d\n",i,c[i]),flag=1;
- if(!flag) printf("NULL");
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2778076.html