旅行计划
题意
大意是给出n个城市以及他们之间的道路,求从1点到其他各点(以各点为终点)所经过的最多城市的数量
思路
其实很明显可以想到dp的部分。但是如何dp是一个问题。这个dp的状态转移其实并不难,只需要从源点转移过来就ok。但是我们需要想到应该从哪个点开始去dp。
这里就需要满足dp的无后效性,即我们之前的状态不应该去依赖于之后的状态。我们可以采用一步拓扑排序来解决这个问题,因为拓扑排序正好可以将这个图进行层次的排序。
code
const int nn = 1e5+10; int n,m; vector<int> ve[nn]; int f[nn]; int ru[nn]; int ts[nn];//存放拓扑序 int cnt = 0; void topsort(){ queue<int> q; for(int i=1;i<=n;i++){ if(ru[i]==0){ q.push(i); ts[++cnt]=i; } } while(!q.empty()){ int u = q.front();q.pop(); for(int i=0;i<ve[u].size();i++){ int v = ve[u][i]; ru[v]--; if(ru[v]==0) q.push(v),ts[++cnt]=v; } } } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0); cin>>n>>m; int x,y; for(int i=1;i<=m;i++){ cin>>x>>y; ve[x].push_back(y); ru[y]++; } topsort(); for(int i=1;i<=n;i++) f[i]=1; for(int i=1;i<=n;i++){ int u = ts[i]; for(int j=0;j<ve[u].size();j++){ int v = ve[u][j]; f[v] = max(f[v],f[u]+1); } } for(int i=1;i<=n;i++) cout<<f[i]<<endl; }
神经网络
题意
大意是给出n个神经元,给出每个神经元的状态参数和阈值参数,给出有向边与权值。给出一个计算最终状态参数的公式。当状态参数>0时可以进行传递。最后求出传输层大于0的信息。
思路
确定输入层入队,输出层计算和阈值的关系
通过边关系确定输出层
在拓扑排序过程中计算最终的状态参数
code
const int nn = 110; int a[nn][nn]; int st[nn]; int ed[nn]; bool is_out[nn]; bool is_inq[nn]; bool sign[nn][nn]; queue<int> q; int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0); int n,p; cin>>n>>p; for(int i=1;i<=n;i++){ is_out[i] = is_inq[i] = false; cin>>st[i]>>ed[i]; if(st[i]>0){ q.push(i); is_inq[i] = true; }else st[i]-=ed[i]; } int x,y,z; for(int i=1;i<=p;i++){ cin>>x>>y>>z; a[x][y] = z; sign[x][y] = true; is_out[x] = true; } while(!q.empty()){ int u = q.front();q.pop(); if(st[u]<=0) continue; for(int i=1;i<=n;i++){ if(sign[u][i]){ st[i]+=a[u][i]*st[u]; if(!is_inq[i]){ q.push(i); is_inq[i] = true; } } } } bool flag = false; for(int i=1;i<=n;i++){ if(!is_out[i]&&st[i]>0){ flag = true; cout<<i<<' '<<st[i]<<endl; } } if(!flag) cout<<"NULL"<<endl; }