题解

115 条题解

  • 7
    @ 2017-05-08 07:56:49
    /*
    表示很久以前就看到了这道题
    一直不敢做啊(Orz原因是因为题目太长看不懂)
    关键是vijos上的那个∑公式看不清 所以给了我逃避的理由2333
    现在终于下定决心好好做一下
    其实发现也不难的(虽然自己一开始没想到这种做法(害羞~))
    这题好像有点类似拓扑排序的样子
    涉及到了入度和出度酱紫~
    我们从输入点开始传递C值,如果C为正则可以传递。
    注意到只有当一个结点的所有入度全部传递完成之后这个结点才可以进行传递,而且结点传递之前需要检查C的正负。
    用in[],out[]分别记录入度和出度,用一个队列维护入度已经求完的结点,边我们可以用邻接向量存
    考虑它所有出度的终点,考虑完成后出队,对于考虑结点而言,对所有出度的in减1,同时判断是否可以入队。
    这样其实就很简单了,输出最后网络输出层的时候,我们可以明确当且仅当out[i]=0时(即出度为0)
    i点才是最后网络输出层其中的一个点
    然后我们就判断所有的最后网络输出层的点有无正值
    如果有的话说明有兴奋状态,就输出
    如果一个都没有就输出NULL
    题目还是很简单的没有什么难点,主要是要看懂题目意思
    唉说到底还是考语文啊(友尽><)
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int Maxn=205;
    struct Edge
    {
        int from,to,w;
        Edge(int from,int to,int w):from(from),to(to),w(w){} 
    };
    vector<Edge> edges;
    vector<int> g[Maxn];
    queue<int> q;
    int in[Maxn],out[Maxn];
    int c[Maxn],u[Maxn];
    int n,m;
    
    void addEdge(int from,int to,int w)
    {
        edges.push_back(Edge(from,to,w));
        int d=edges.size();
        g[from].push_back(d-1);
        in[to]++,out[from]++;
    }
    
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>c[i]>>u[i];
            if(c[i]>0)
                q.push(i);
            if(c[i]==0)
                c[i]-=u[i];
        }
        int x,y,v;
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y>>v;
            addEdge(x,y,v);
        }
    
        while(!q.empty())
        {
            int k=q.front();    q.pop();
            if(c[k]>0)
            {
                for(int i=0;i<g[k].size();i++)
                {
                    int v=edges[g[k][i]].to;
                    int w=edges[g[k][i]].w;
                    c[v]+=w*c[k];
                    if(!(--in[v]))
                        q.push(v);
                }
            }
        }
        bool f=1;
        for(int i=1;i<=n;i++)
            if(!out[i]&&c[i]>0)
            {
                cout<<i<<" "<<c[i]<<endl;
                f=0;
            }
        if(f)
            cout<<"NULL"<<endl;
        return 0;
    }
         
    
  • 4
    @ 2016-10-29 18:27:12

    再来一个用队列top排序的

    我是萌萌哒的分界线

    #include<cstdio>
    #include<queue>
    #include<cstring> 
    using namespace std;
    const int N=201;
    queue<int>top;
    int u[N],c[N],w[N][N],vis[N],in[N],out[N];
    int n,p,i,j,x,y,z,f;
    void read()
    {
        memset(w,1,sizeof(w));
        scanf("%d%d",&n,&p);
        for(i=1;i<=n;i++)
            scanf("%d%d",&c[i],&u[i]);
        for(i=1;i<=p;i++)
            scanf("%d%d%d",&x,&y,&z),
            w[x][y]=z,
            in[y]++,out[x]++;
        for(i=1;i<=n;i++)
            if(in[i])
                c[i]-=u[i];
            else if(c[i]>0)
                top.push(i);
    }
    void work()
    {
        while(!top.empty())
        {
            int i=top.front(),j,flag=0;top.pop();
            for(j=1;j<=n;j++)
                if(w[i][j]!=16843009)
                {
                    flag=1;
                    c[j]+=w[i][j]*c[i];
                    in[j]--;
                    if(!in[j]&&c[j]>0) top.push(j);
                }
        }
        for(i=1;i<=n;i++)
            if(!out[i]&&c[i]>0)
                printf("%d %d\n",i,c[i]),f++;
        if(!f) printf("NULL");
    }
    int main()
    {
        read();work();
    return 0;
    }
    

    我是萌萌哒的分界线

    • @ 2017-10-23 22:18:39

      if(w[i][j]!=16843009)
      请问一下这是什么意思?谢谢

    • @ 2018-06-13 15:28:12

      @Rafe: 这是memset赋值为1的结果

    • @ 2018-07-05 16:21:13

      @Rafe: memset(w,1,sizeof(w))
      因为的数组a是字符型的,字符型占据内存大小是1Byte,而memset函数也是以字节为单位进行赋值的,所以你输出没有问题。而第二个程序a是整型的,使用 memset还是按字节赋值,这样赋值完以后,每个数组元素的值实际上是0x01010101即十进制的16843009。
      如果用memset(a,1,20),就是对a指向的内存的20个字节进行赋值,每个都用数1去填充,转为二进制后,1就是00000001,占一个字节。一个int元素是4字节,合一起是0000 0001,0000 0001,0000 0001,0000 0001,转化成十六进制就是0x01010101,就等于16843009,就完成了对一个int元素的赋值了。

    • @ 2018-07-05 16:24:09

      @xiao_sutian: @Rafe: @Rafe: https://baike.baidu.com/item/memset/4747579?fr=aladdin
      xiongdizijikankan buxie

  • 2
    @ 2016-10-26 21:25:07
    #include<cstdio>
    const int N=201;
    struct tree
    {
        int num,son[N];
    }t[N];
    int u[N],c[N],w[N][N],in[N],out[N];
    int n,p,i,j,x,y,z,f;
    int main()
    {
        scanf("%d%d",&n,&p);
        for(i=1;i<=n;i++)
            scanf("%d%d",&c[i],&u[i]);
        for(i=1;i<=p;i++)
            scanf("%d%d%d",&x,&y,&z),
            w[x][y]=z,
            out[x]++,in[y]++,
            t[x].son[++t[x].num]=y;
        for(i=1;i<=n;i++)
            if(!in[i]&&out[i]&&c[i]>0)
                    for(j=1;j<=t[i].num;j++)
                    in[t[i].son[j]]--,
                    c[t[i].son[j]]+=w[i][t[i].son[j]]*c[i],
                    c[t[i].son[j]]-=in[t[i].son[j]]==0?u[t[i].son[j]]:0;
        for(i=1;i<=n;i++)
            if(!out[i]&&c[i]>0)
                printf("%d %d\n",i,c[i]),
                f=1;
        if(!f)
            printf("NULL");
    return 0;
    }
    

  • 1
    @ 2020-12-23 21:38:31

    本题是一个裸的拓补排序题,与NOIP2020 T1 有异曲同工之妙,不同点在于今年的弱智题目卡了高精。
    与他人不同的是,我这里选择了DFS 做法,与不同的队列做法不大一样,但是实质上没有任何差别,只不过是将广度优先改为了深度优先而已。

    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<set>
    #define mp(a,b) make_pair(a,b)
    
    using namespace std;
    const int maxn = 210;
    vector<pair<int,int> > e[maxn];
    vector<int> Q;
    int c[maxn];
    int n,m;
    int u[maxn];
    bool inv[maxn];
    bool t[maxn];
    int ins[maxn];
    inline void input() {
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++) {
            scanf("%d",&c[i]);
            if(c[i] != 0) Q.push_back(i);
            scanf("%d",&u[i]);
        }
        for(int i = 1; i <= m; i++) {
            int x,y,val;
            scanf("%d%d%d",&x,&y,&val);
            t[x] = true;
            e[x].push_back(mp(y,val));
            ins[y]++;
        }
        return ;
    }
    void dfs(int now) {
        for(auto x:e[now]) {
            int t1 = now,t2 = x.first;
            c[t2] += (x.second * c[t1]);
            ins[t2]--;
            if(!ins[t2]) {
                c[t2] -= u[t2];
                if(c[t2] > 0) dfs(t2);
            }
        }
        return;
    }
    inline void work() {
        for(auto x:Q) dfs(x);
        return;
    }
    inline void print() {
        bool flag = true;
        for(int i = 1; i <= n; i++) {
            if(t[i] == 0 && c[i] > 0) printf("%d %d\n",i,c[i]),flag = false;
        }
        if(flag) puts("NULL");
        return;
    }
    int main() {
        input();
        work();
        print();
        return 0;//直接复制粘贴会爆蛋,建议理解了代码之后自己打一遍。
    }
    
  • 1
    @ 2017-09-11 22:54:33

    拓扑序判断下一个神经元,bfs就可以过了......

    #include <stdio.h>
    #include <vector>
    #include <queue>
    using namespace std;
    const int maxn=505;
    
    int w[maxn][maxn];
    int c[maxn],cut[maxn];
    vector<int>vec[maxn];
    int in[maxn],out[maxn];
    priority_queue<int,vector<int>,greater<int> >q;
    int n,p;
    int ans[maxn],num[maxn],cnt;
    
    void bfs()
    {
        for(int i=1;i<=n;i++)
            if(in[i]==0) q.push(i);
        while(!q.empty())
        {
            int u=q.top();q.pop();
            if(out[u]==0)
            {
                ans[++cnt]=c[u];
                num[cnt]=u;
                continue;
            }
            int d=vec[u].size();
            for(int i=0;i<d;i++)
            {
                int v=vec[u][i];
                if(c[u]>=1) c[v]+=c[u]*w[u][v];
                out[u]--;
                in[v]--;
                if(in[v]==0) c[v]-=cut[v],q.push(v);
            }
        }
    }
    
    int main()
    {
        scanf("%d%d",&n,&p);
        for(int i=1;i<=n;i++) scanf("%d%d",&c[i],&cut[i]);
        for(int i=1;i<=p;i++)
        {
            int u,v,val;
            scanf("%d%d%d",&u,&v,&val);
            w[u][v]=val;
            vec[u].push_back(v);
            out[u]++,in[v]++;
        }
        bfs();
        bool flag=false;
        for(int i=1;i<=cnt;i++)
            if(ans[i]>=1)
            {
                flag=true;
                break;
            }
        if(flag)
        {
            for(int i=1;i<=cnt;i++)
                if(ans[i]>=1)
                    printf("%d %d\n",num[i],ans[i]);        
        }
        else printf("NULL");
        return 0;
    }
    
  • 0
    @ 2018-10-15 16:24:27

    这个居然是也算NOIP提高组?笑杀老夫

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    struct zhu{
        int v,w,next;
    }e[40010];
    struct point{
        int num;
        int c;
        int u;
        bool operator < (point &xx)const{
            return xx.num<num;
        }
        point(){}
        point(int num,int c,int u):num(num),c(c),u(u){}
    }r[210];
    int head[210],inq[210],size=0;
    priority_queue <int,vector<int>,greater<int> > q;
    int ok=0;
    inline void add(int u,int v,int w){
        e[size].v=v;
        e[size].w=w;
        e[size].next=head[u];
        head[u]=size++;
    } 
    int main(){
        memset(head,-1,sizeof(head));
        int n,p;
        scanf("%d%d",&n,&p);
        for(int i=1;i<=n;++i){
            int c,u;
            scanf("%d%d",&c,&u);
            r[i]=point(i,c,u);
            if(c>0){
                r[i].c+=u;
                q.push(i);
            }
        }
        for(int i=1;i<=p;++i){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        while(!q.empty()){
            int u=q.top();
            q.pop();
            r[u].c-=r[u].u;
            if(r[u].c<=0)continue;
            if(head[u]==-1){
                ok=1;
                printf("%d %d\n",u,r[u].c);
            }
            for(int i=head[u];i!=-1;i=e[i].next){
                int v=e[i].v;
                r[v].c+=e[i].w*r[u].c;
                if(!inq[v]){
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
        if(!ok)printf("NULL");
        return 0;
    }
    
  • 0
    @ 2018-02-05 16:57:08
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int maxN = 200 + 5;
    
    int W[maxN][maxN]; //有向边的权值
    bool linked[maxN][maxN]; //linked[u][v] = u->v是否有一条有向边相连
    int U[maxN], C[maxN];
    int inDeg[maxN], outDeg[maxN]; //分别记录每个点的入度和出度
    int N, P;
    
    void input()
    {
        scanf("%d%d", &N, &P);
        for (int i = 1; i <= N; i++)
            scanf("%d%d", C + i, U + i);
        for (int u, v, w, i = 1; i <= P; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            outDeg[u] += 1;
            inDeg[v] += 1;
            W[u][v] = w;
            linked[u][v] = true;
        }
    }
    
    void bfs()
    {
        queue<int> que;
        for (int i = 1; i <= N; i++)
            if (inDeg[i] == 0) //先将所有入度为0的点(也就是输入层)加入队列
            {
                que.push(i);
                C[i] += U[i]; //这里与while循环内的C[cur] -= U[cur]对应
                //输入层的C[i]先加后减所以不变,其他层的C[i]会减去它的阈值
            }
    
        while (!que.empty()) //BFS过程可以保证每个节点都入队一次
        {
            int cur = que.front();
            que.pop();
    
            C[cur] -= U[cur]; //减去当前点的阈值
            for (int to = 1; to <= N; to++)
            {
                if (!linked[cur][to])
                    continue;
                if (C[cur] > 0)
                    C[to] += (W[cur][to] * C[cur]);
                if (--inDeg[to] == 0) //通过删边来判断下一个节点是否已接收来自上一层的全部信息
                    que.push(to);
            }
        }
    }
    
    int main()
    {
        input();
        bfs();
        bool outputted = false; //标记是否已经输出某个节点
        for (int i = 1; i <= N; i++)
            if (outDeg[i] == 0 && C[i] > 0) //这里Vijos题面描述有误,仅当C[i] > 0时才输出
                //outDeg[i] == 0表示该节点属于输出层(这里包含了节点既是输入层也是输出层的情况)
            {
                printf("%d %d\n", i, C[i]);
                outputted = true;
            }
        if (!outputted)
            printf("NULL");
        return 0;
    }
    
  • 0
    @ 2017-11-27 18:34:45

    注意m=0的情况,即输入层就是输出层

  • 0
    @ 2017-05-21 23:46:18

    这题好蠢,浪费时间。只要一层一层遍历就行。我还以为遍历完一层那些非输出层但是c>0的还要继续发信号。

  • 0
    @ 2017-05-20 09:40:28

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #define rep(i,n) for(i=1;i<=n;i++)
    using namespace std;
    int v[201], p[201], f[201];
    int ru[201];
    int h[201];
    int que[201];
    int chu[201];
    int x, y;
    struct node{
    int a, b, c, n;
    }d[100001];
    int max1;
    int f1;
    int read(){
    int x, f = 1;
    char ch;
    while(ch=getchar(),ch<'0'||ch>'9'){
    if(ch=='-') f = -1;
    }
    x = ch-48;
    while(ch=getchar(),'0'<=ch&&ch<='9'){
    x = x * 10 + ch - 48;
    }
    return x*f;
    }
    int main(){
    int i, j, n, m, a, b, c;
    n = read(); m = read();
    rep(i,n){
    v[i] = read(); p[i] = read();
    if(!v[i]){
    v[i] = -p[i];
    }
    }
    rep(i,m){
    a = read(); b = read(); c = read();
    d[i].a = a; d[i].b = b; d[i].c = c;
    d[i].n = h[a]; h[a] = i;
    ru[b]++;
    chu[a]++;
    }
    rep(i,n) if(!ru[i]) que[++y] = i;
    rep(x,y){
    a = que[x];
    for(i = h[a]; i; i = d[i].n){
    b = d[i].b;
    v[b] += v[a]*d[i].c;
    ru[b]--;
    if(!ru[b]&&v[b]>0){
    que[++y] = b;
    }
    }
    }
    rep(i,n){
    if(v[i]>0&&!chu[i]){
    printf("%d %d\n", i, v[i]);
    f1 = 1;
    }
    }
    if(!f1) printf("NULL\n");

    return 0;
    }
    图与样例不符啊!!!害我做了好久!!一直不知道输出的是输出层!!!!!

  • 0
    @ 2016-10-24 16:21:01

    不需要搜索
    c++
    #include<iostream>
    #include<vector>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    struct node
    {
    int output,bias;
    bool ru=0,chu=0;
    vector<int*> value;
    vector<int>outedge,weight;
    void calc()
    {
    if(ru)output = 0;
    for(int i=0;i<value.size();++i)
    output+=(*value[i])*weight[i];
    output-=bias;
    if(output<=0)output=0;
    }
    }nodes[210];
    bool vis[210];
    vector<vector<int>> ann;//用于保存神经元之间的关系
    int n,p,layer;
    int main()
    {
    //读入数据
    cin>>n>>p;
    for(int i=1;i<=n;++i)
    scanf("%d%d",&nodes[i].output,&nodes[i].bias);
    for(int i=1;i<=p;++i)
    {
    int a,b,w;
    scanf("%d%d%d",&a,&b,&w);
    nodes[b].value.push_back(&nodes[a].output);
    nodes[a].outedge.push_back(b);
    nodes[b].weight.push_back(w);
    nodes[b].ru=nodes[a].chu=1;
    }
    ann.resize(1);
    for(int i=1;i<=n;++i)
    if(!nodes[i].ru)ann[0].push_back(i);
    //建立神经网络
    do{
    memset(vis,0,sizeof(vis));
    ann.resize(layer+2);
    for(int i=0;i<ann[layer].size();++i)
    for(int j=0;j<nodes[ann[layer][i]].outedge.size();++j)
    {
    int target = nodes[ann[layer][i]].outedge[j];
    if(vis[target])continue;
    ann[layer+1].push_back(target);
    vis[target]=1;
    }
    }while(ann[++layer].size());
    ann.resize(layer--);
    //计算
    for(int i=1;i<=ann.size();++i)
    for(int j=0;j<ann[i].size();++j)
    nodes[ann[i][j]].calc();
    bool flag = 1;
    //输出
    for(int i=1;i<=n;++i)
    if(!nodes[i].chu&&nodes[i].output)
    {
    cout<<i<<" "<<nodes[i].output<<endl;
    flag = 0;
    }
    if(flag)cout<<"NULL"<<endl;
    return 0;
    }

  • 0
    @ 2016-08-19 10:29:14

    那条式子是什么意思

  • 0
    @ 2016-08-01 18:42:20

    为什么会有负数啊。。
    坑。。

  • 0
    @ 2016-04-19 21:04:24

    读懂题目就是胜利!
    *************************我是萌萌哒的分界线*************************
    Tip1.边有负数
    Tip2.边为0也算有边
    Tip3.Ci>0即可向下一层传输
    Tip4.最后只输出Ci>0的解
    Tip5.输入层由于没有上一层节点,不需要减去阈值

    PS.别问我为什么知道这么多,想想通过率我就心疼……
    *************************我是萌萌哒的分界线*************************
    ```c++
    /*
    Name: Neural Network
    Author: GoldenSun
    Description: NOIP2003 High
    */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int n,p;
    int c[100],u[100];
    int w[100][100];
    int w_hash[100][100];
    int q[100];
    int q_count=0;
    int d[100];
    int maxd=0;
    int c_hash[100];
    int bfs(int q_i)
    {
    int j;

    c[q_i]-=u[q_i];

    for(j=0;j<n;j++)
    if(w_hash[q_i][j]==1)
    {
    if(c_hash[j]==0)
    {
    c_hash[j]=1;
    q[q_count++]=j;
    }

    if(d[j]<d[q_i]+1)
    d[j]=d[q_i]+1;

    if(maxd<d[j])
    maxd=d[j];

    if(c[q_i]>0)
    c[j]+=w[q_i][j]*c[q_i];
    }

    return 0;
    }
    int main()
    {
    memset(c,0,sizeof(c));
    memset(u,0,sizeof(u));
    memset(w,0,sizeof(w));
    memset(q,0,sizeof(q));
    memset(d,0,sizeof(d));
    memset(c_hash,0,sizeof(c_hash));
    memset(w_hash,0,sizeof(w_hash));

    int i;
    int t1,t2;
    int flag=0;

    scanf("%d%d",&n,&p);
    for(i=0;i<n;i++)
    {
    scanf("%d%d",&c[i],&u[i]);

    if(c[i]>0)
    {
    c_hash[i]=1;
    q[q_count++]=i;
    c[i]+=u[i];
    }
    }
    for(i=0;i<p;i++)
    {
    scanf("%d%d",&t1,&t2);
    scanf("%d",&w[t1-1][t2-1]);
    w_hash[t1-1][t2-1]=1;
    }

    for(i=0;i<q_count;i++)
    bfs(i);

    for(i=0;i<n;i++)
    {
    if(maxd==d[i]&&c[i]>0)
    {
    flag=1;
    printf("%d %d\n",i+1,c[i]);
    }
    }
    if(flag==0)
    printf("NULL\n");

    return 0;
    }
    ```
    *************************我是萌萌哒的分界线*************************
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 632 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 632 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 632 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 632 KiB, score = 20
    测试数据 #4: Accepted, time = 0 ms, mem = 632 KiB, score = 20
    Accepted, time = 15 ms, mem = 632 KiB, score = 100

  • 0
    @ 2016-03-17 21:57:42

    这道题确实神经。。。温馨提示:输入层不用减去阀值^-^..
    测试数据 #0: Accepted, time = 0 ms, mem = 964 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 964 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 968 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 964 KiB, score = 20
    测试数据 #4: Accepted, time = 0 ms, mem = 964 KiB, score = 20
    Accepted, time = 0 ms, mem = 968 KiB, score = 100

    type    int=longint;
    var
            i,n,p,tail,head:int;
            c,u,a,b,d:array[0..201]of int;
            flag:boolean;
            f,s:array[0..201]of boolean;
            w:array[0..201,0..201]of int;
    procedure hunter;
    var
            i:int;
    begin
            readln(n,p);
            for i:=1 to n do read(c[i],u[i]);
            for i:=1 to n do
            begin
                    f[i]:=true;
                    s[i]:=true;
            end;
            fillchar(w,sizeof(w),0);
            for i:=1 to p do read(a[i],b[i],w[a[i],b[i]]);
            for i:=1 to p do f[a[i]]:=false;
            tail:=0;
            for i:=1 to n do if c[i]>0 then
            begin
                    inc(tail);
                    d[tail]:=i;
                    s[i]:=false;
                    c[i]:=c[i]+u[i];
            end;
            head:=1;
            flag:=true;
    end;
    
    begin
            hunter;
            repeat
                    c[d[head]]:=c[d[head]]-u[d[head]];
                    if c[d[head]]>0 then
                    begin
                    for i:=1 to n do if w[d[head],i]<>0 then
                    begin
                            c[i]:=c[i]+w[d[head],i]*c[d[head]];
                            if s[i] then
                            begin
                                    inc(tail);
                                    d[tail]:=i;
                                    s[i]:=false;
                            end;
                    end;
                    end;
                    inc(head);
            until   head>tail;
            for i:=1 to n do if f[i] and(c[i]>0) then
            begin
                    writeln(i,' ',c[i]);
                    flag:=false;
            end;
            if flag then writeln('NULL');       
    end.
    
    • @ 2016-08-21 22:47:21

      阀值。。。阈值吧。。。

  • 0
    @ 2015-11-28 10:32:45

    #include<iostream>
    #include<iomanip>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cctype>
    #include<cstdlib>
    #define N 10000
    using namespace std;
    int a[N][N],c[N],u[N];
    int in[N],out[N],q[N];
    double sum=1,now;
    int fr,tail,flag;
    int main()
    {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    cin>>c[i]>>u[i];
    c[i]-=u[i];
    }
    for(int i=1;i<=m;i++)
    {
    int x,y,z;
    cin>>x>>y>>z;
    a[x][y]=z;
    in[y]++;
    out[x]++;
    }
    for(int i=1;i<=n;i++)
    {
    if(!in[i])q[++fr]=i;
    }
    while(fr>tail)
    {
    int k=q[++tail];
    for(int i=1;i<=n;i++)
    {
    if(a[k][i])
    {
    c[i]+=c[k]*a[k][i];
    in[i]--;
    if(!in[i])q[++fr]=i;
    }
    }
    }
    for(int i=1;i<=n;i++)
    {
    if(!out[i]&&c[i]>0){cout<<i<<' '<<c[i]<<endl;flag=1;}
    }
    if(flag==0)cout<<"NULL";
    return 0;
    }

  • 0
    @ 2015-10-16 20:50:29

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    using namespace std;
    const int MAXN = 300;

    int c[MAXN+10], u[MAXN+10], v[MAXN+10], used[MAXN+10], ans[MAXN+10];
    vector<pair<int, int> > map[MAXN+10];

    int slen(int* a){
    for(int i=MAXN; i>=1; i--)
    if(a[i])
    return i;
    return 0;
    }

    void bfs(int* a){
    int len = slen(a);
    int xin[MAXN+10] = {}, use[MAXN+10] = {}, flag = 1;
    for(int i=1; i<=len; i++)
    if(c[a[i]] > 0){
    for(int j=0; j<map[a[i]].size(); j++){
    int bri = map[a[i]][j].first;
    c[bri] += map[a[i]][j].second*c[a[i]];
    if(use[bri]) continue;
    use[bri] = 1;
    xin[flag++] = bri;
    }
    }
    for(int i=1; i<flag; i++)
    c[xin[i]] -= u[xin[i]];
    if(flag == 1) {
    for(int i=1; i<=MAXN; i++)
    ans[i] = a[i];
    return;
    }
    bfs(xin);
    }

    int main()
    {
    int n, p;
    scanf("%d%d", &n, &p);
    for(int i=1; i<=n; i++)
    scanf("%d%d", &c[i], &u[i]);
    int flag = 1;
    v[1] = 1;
    for(int i=1; i<=p; i++){
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    map[x].push_back(make_pair(y, z));
    if(c[x]>0 && !used[x]) v[flag++] = x, used[x] = 1;
    }
    bfs(v);
    int len = slen(ans), qi = 1;;
    sort(&ans[1], &ans[1]+len);
    for(int i=1; i<=len; i++)
    if(c[ans[i]] > 0){
    printf("%d %d\n", ans[i], c[ans[i]]);
    qi = 0;
    }
    if(qi)
    printf("NULL");
    return 0;
    }
    用BFS做的,,虽然A了,但并不知道算法到底对不对。。。
    还有,这题描述太难懂了

  • 0
    @ 2015-10-01 14:37:34

    按照拓扑序计算即可
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 1448 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 1452 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 1444 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 1452 KiB, score = 20
    测试数据 #4: Accepted, time = 0 ms, mem = 1444 KiB, score = 20
    Accepted, time = 0 ms, mem = 1452 KiB, score = 100

    #include<bits/stdc++.h>

    using namespace std;

    const int maxn = 209;

    struct edge {
    int to, w;
    edge* next;
    } E[100000], *pt = E, *head[maxn];

    inline void addedge(int u, int v, int w) {
    pt->to = v; pt->w = w; pt->next = head[u]; head[u] = pt++;
    }

    int deg[maxn], N, F[maxn], C[maxn];
    bool output[maxn];

    void init() {
    memset(deg, 0, sizeof deg);
    memset(output, 0, sizeof output);
    int m;
    scanf("%d%d", &N, &m);
    for(int i = 0; i < N; i++) {
    scanf("%d%d\n", F + i, C + i);
    C[i] = F[i] ? F[i] : -C[i];
    }
    while(m--) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w); u--; v--;
    deg[v]++;
    output[u] = true;
    addedge(u, v, w);
    }
    }

    void dfs(int x) {
    for(edge* e = head[x]; e; e = e->next) {
    C[e->to] += e->w * C[x];
    if(!--deg[e->to] && C[e->to] > 0) dfs(e->to);
    }
    }

    int main() {

    init();
    for(int i = 0; i < N; i++)
    if(F[i]) dfs(i);
    bool flag = false;
    for(int i = 0; i < N; i++) if(!output[i] && C[i] > 0) {
    flag = true;
    printf("%d %d\n", i + 1, C[i]);
    }
    if(!flag)
    puts("NULL");

    return 0;
    }

  • 0
    @ 2015-06-01 10:28:54

    直接模拟做的,开始忘记考虑权值为非正数(直接用k[i][j]>0判断有没有边)结果WA了好多次

    #include<stdio.h>
    int main( )
    {

    int n,p,c[205]={0},u[205]={0},k[205][205],i,j,a,b,flag=0,d,flag2=0,flag3=0,pd[205][205];

    for(i=1;i<=204;i++)
    for(j=1;j<=204;j++)
    {k[i][j]=0;pd[i][j]=0;}

    scanf("%d %d",&n,&p);

    for(i=1;i<=n;i++)
    scanf("%d %d",&c[i],&u[i]);

    for(i=1;i<=p;i++)
    {
    scanf("%d %d %d",&a,&b,&d);
    k[b][a]=d;
    pd[b][a]=1;
    }

    for(i=1;i<=n;i++)
    {
    for(j=i-1;j>=1;j--)
    if (pd[i][j]==1 && c[j]>0) {c[i]=c[i]+c[j]*k[i][j];flag3=1;}

    if(flag3==1) c[i]=c[i]-u[i];
    flag3=0;
    }

    for(i=1;i<=n;i++)
    {
    for(j=i;j<=n;j++)
    if(pd[j][i]==1) flag2=1;

    if (flag2==0 && c[i]>0) {printf("%d %d\n",i,c[i]);flag=1;}
    flag2=0;
    }

    if(flag==0) printf("NULL");

    return 0;
    }

信息

ID
1105
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
4324
已通过
1253
通过率
29%
被复制
13
上传者