旅行计划

题意

大意是给出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;
}