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
我以为说的是就剩一个点没过其他全过了→ →