2019-05-21 P 1038ニューラルネットワーク

タイトルリンク:https://www.luogu.org/problemnew/show/P1038

                ：
#include
#include
#include
#include
#include
using namespace std;
const int maxn=101;
typedef vector vec;
struct Node{
    int v,w;
    Node(int v=0,int w=0):v(v),w(w){}
}; 
vectorG[maxn];
int n,p,U[maxn],C[maxn],in[maxn],out[maxn];

vec solve(){
    vec ans;
    queueque;
    for(int i=1;i<=n;i++){
        if(in[i]==0) {
            U[i]=0;//             ，     0 
            que.push(i);
        }
    }
    while(!que.empty()){
        int u=que.front(); que.pop();
        C[u]-=U[u];//    
        for(int i=0;i0) C[v]+=w*C[u];//        ，             
        } 
    }
    for(int i=1;i<=n;i++){
        if(out[i]==0 && C[i]>0){
            ans.push_back(i);
        }
    }
    return ans; 
}
int main(void){
    cin>>n>>p;
    for(int i=1;i<=n;i++) cin>>C[i]>>U[i];
    for(int i=1;i<=p;i++){
        int u,v,w;
        cin>>u>>v>>w;
        in[v]++;
        out[u]++;
        G[u].push_back(Node(v,w));      
    }
    vec ans=solve();
    if(ans.size()==0) cout<

         ，      bfs        ：
#include
#include
#include
#include
#include
using namespace std;

const int maxn=101;
struct Node{
    int v,w;
    Node(int v=0,int w=0):v(v),w(w){} 
};
vector Adj[maxn];
int n,p,U[maxn],C[maxn],level[maxn],in[maxn],out[maxn],used[maxn];

vector solve(){
    queueque;
    for(int i=1;i<=n;i++){
        if(in[i]==0 && C[i]>0){//               
            que.push(i);//     
            used[i]=true;//         
        }
    }
    while(!que.empty()){//  bfs             
        int u=que.front(); que.pop();
        //                 ，    
        if(in[u]!=0) C[u]-=U[u];//           
        if(C[u]<=0) continue;//             ，         
        for(int i=0;ivec;
    for(int i=1;i<=n;i++)
        if(out[i]==0 && C[i]>0)//      
            vec.push_back(i);
    return vec;
}
int main(void){
    cin>>n>>p;
    for(int i=1;i<=n;i++) cin>>C[i]>>U[i];
    int u,v,w;
    for(int i=1;i<=p;i++){
        cin>>u>>v>>w;
        Adj[u].push_back(Node(v,w));
        in[v]++;//         ，             
        out[u]++;
    }
    vector vec = solve();
    
    bool isnull; 
    if(vec.size()==0) isnull=true;
    else isnull=false;
    
    if(isnull) cout<