可读性超强 不信进来看 样例全能过

P1600 [NOIP2016 提高组] 天天爱跑步

czyhbodn @ 2017-08-26 21:11:13

但是一个点没过 谁能告诉下原因

#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
const int maxn=100;
int f[maxn][maxn][maxn];
int w[maxn];
int map[maxn][maxn];
int b[maxn];//父亲节点 
int n,m;//节点 玩家 
int pep=0;
int tj[maxn];
void ff(int d)
{
    int time=-1;
    int a[maxn];
    int aa=1;
    a[1]=d;
    while(b[d])
    {
        aa++;
        d=b[d];
        a[aa]=d;                        // cout<<aa<<" ";
    }
    for(int i=aa;i>=1;i--)
    {
        time++;                      // cout<<time<<" ";
        f[pep][time][ a[i] ]=1;     // cout<<pep<<" "<<time<<" "<<a[i]<<endl;
        if(w[ a[i] ] == time)
        tj[ a[i] ]++;
    }
}
void bfs(int begin ,int end)
{
    if(begin == end) {b[begin]=0; ff(begin); return ;}
    int q[maxn],head=0,tail=1;
    int vis[maxn];
    memset(vis,0,sizeof(vis));
    q[1]=begin;b[begin]=0;vis[begin]=1;
    do
    {
        head++;
        for(int i=1;i<=n;i++)
          if(map[ q[head] ][i]==1 && vis[i]==0)
            {
                tail++;
                q[tail]=i;
                b[i]=q[head];
                vis[i]=1;
                if(i==end)
                {
                    head=tail;
                    ff(i);
                    break;
                }
            }
    }
    while(head<tail);
}
int main()
{
    cin>>n>>m;
    //读图 
    int jing=n-1;
    while(jing--)
    {
        int u,v;
        cin>>u>>v;
        map[u][v]=map[v][u]=1;
     } 
     //读观察员 
     for(int i=1;i<=n;i++)
     {cin>>w[i];       }            //  cout<<w[i]<<" ";     }
     //读玩家存最短路径 
     memset(f,0,sizeof(f));
     while(m--)
     {
         int begin,end;
         cin>>begin>>end;
         pep++;
         bfs(begin,end);
     }
       //输出
       for(int i=1;i<=n-1;i++)
        cout<<tj[i]<<" ";  cout<<tj[n]<<endl;
        //cout<<(double)clock()/CLOCKS_PER_SEC;
     return 0;
}

by I_AM_HelloWord @ 2017-08-26 22:39:12

你样例没过敢交么【手动滑稽】


by czyhbodn @ 2017-08-27 15:57:29

@I_AM_HelloWord 我样例全过了


by I_AM_HelloWord @ 2017-08-27 16:03:28

@djl001103 可是就2个样例,过了能说明什么问题呢。


by rushcheyo @ 2017-09-12 19:26:54

n 是 3e5 哥哥……而且以您的水平做这题是不是有些不妥当?


by strangers @ 2017-09-13 03:20:55

这题要是爆搜都能够过就真是有鬼了滑稽


by yyy14159 @ 2017-09-17 17:49:57

这题最小的数据也是900+吧...


by youken @ 2017-10-03 20:33:16

蓝名受到红名嘲讽。。手动害怕


by suncongbo @ 2017-10-20 15:12:59

突然想起了bzoj神帖


by santongding @ 2018-02-17 12:12:42

我以为说的是就剩一个点没过其他全过了→ →


|