社区讨论
萌新求助
灌水区参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo7jpxiw
- 此快照首次捕获于
- 2023/10/27 02:56 2 年前
- 此快照最后确认于
- 2023/10/27 02:56 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int to,w,v;
};
queue<int>s;
queue<int>l;
vector<Edge> e[102];
int c[102],dep[102],u[102],in[102];
int main(){
memset(dep,0x3f3f3f,sizeof(dep));
int n,p;
for(int i=1;i<=n;i++){
int x,ui;
cin>>x>>ui;
c[i]=x;
u[i]=ui;
}
for(int i=1;i<=p;i++){
int x,y,w;
cin>>x>>y>>w;
in[y]++;
e[x].push_back(Edge{y,w,0});
}
for(int i=1;i<=n;i++)if(!in[i]){s.push(i);dep[i]=1;}
int maxd=0;
while(!s.empty()){
int x=s.front();
for(int i=0;i<e[x].size();i++){
int rt=e[x][i].to;
in[rt]--;
dep[rt]=min(dep[rt],dep[x]+1);
maxd=max(maxd,dep[rt]);
c[rt]+=e[x][i].w*c[x];
if(!in[rt]) {s.push(rt);c[rt]-=u[i];}
}
l.push(x);
}
bool f=false;
while(!l.empty()){
int x=l.front();
if(dep[x]==maxd&&c[x]>0){
cout<<x<<" "<<c[x]<<"\n";
f=true;
}
l.pop();
}
if(!f) cout<<"NULL\n";
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...