文章目錄

• • • • $Result$
      • $Hyperlink$
      • $Description$
      • $Solution$
      • $Code$

$Result$

---

$Hyperlink$

https://www.luogu.com.cn/problem/P1038

---

$Description$

一張神經(jīng)網(wǎng)絡(luò)可以看做一個(gè)$DAG$，它由三種層組成：輸入層，傳輸層，輸出層

輸入層：初始$C_i>0$的層
輸出層：沒有出邊的層
傳輸層：輸入層和輸出層相對(duì)于整張圖的補(bǔ)層

規(guī)定傳輸時(shí)要減去閾值$U_i$，求輸出層經(jīng)過傳輸后仍然滿足$C_i>0$的點(diǎn)，如果沒有，輸出$NULL$

數(shù)據(jù)范圍：$n\le 100$

---

$Solution$

考慮讓初始$C_i\le 0$的提前減去$U_i$，因?yàn)榈竭_(dá)它們必然要減去，它們不可能作為傳輸?shù)钠瘘c(diǎn)
接著用$bfs$遍歷整張圖即可

時(shí)間復(fù)雜度：$O(n+m)$

---

$Code$

#include<queue> #include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std;int c[101],u[101],tot,l[101],n,m,U,V,W; bool vis[101],out[101]; struct node{int next,to,w;}e[100011]; inline void add(int u,int v,int w){e[++tot]=(node){l[u],v,w};l[u]=tot;return;} inline LL read() {char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f; } queue<int>q; signed main() {n=read();m=read();for(register int i=1;i<=n;i++) {c[i]=read();u[i]=read();if(c[i]) q.push(i),vis[i]=true;else c[i]-=u[i];}for(register int i=1;i<=m;i++) U=read(),V=read(),W=read(),add(U,V,W),out[U]=true; while(q.size()){int x=q.front();q.pop();for(register int i=l[x];i;i=e[i].next){int y=e[i].to,w=e[i].w;c[y]+=c[x]*w;if(c[y]>0&&vis[y]==false) q.push(y),vis[y]=true;}}bool flg=true;for(register int i=1;i<=n;i++) if(c[i]>0&&out[i]==false) printf("%d %d\n",i,c[i]),flg=false;if(flg) return puts("NULL")&0; }

總結(jié)

以上是生活随笔為你收集整理的P1038 神经网络的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。