洛谷1041 传染病控制
原题链接
交题记录
16:52 20'
不知道是双向边。。。
16:54 70'
vector忘记判断size了。。。
16:59 80'
sum忘特判1了。。。
17:00 90'
sum忘特判0了。。。还能说什么
17:02 AC
呵呵呵。。。
17:05 AC第二次
把vector换掉了。
题解
我太弱了。。。
这题我只会dfs乱搞
但好像没人用树状数组优化。。。
先把dfn,siz都搞出来
一个点的子树在树状数组中就对应([dfn,dfn+siz))
割掉这个点时把这棵子树都标记为1，回溯再标记为0，(O(log_2siz))
每次搜索把树状数组中标记为0的点数记为(sum)，下一个搜索就得多感染(sum-1)人，然后枚举点割掉就行了
Code
vector版本
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<vector>
#define Fname "epidemic"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=310,maxm=maxn<<1;
int fir[maxn],nxt[maxm],dis[maxm];
int siz[maxn],dfn[maxn],ans=1e9,n;
vector<int>s[maxn];
il vd DFS(int now,int dep=1,int fa=-1){
s[dep].push_back(now);
siz[now]=1,dfn[now]=++dfn[0];
erep(i,now)if(dis[i]^fa)DFS(dis[i],dep+1,now),siz[now]+=siz[dis[i]];
}
int tree[maxn];
il vd add(int p,int k){while(p<=n)tree[p]+=k,p+=p&-p;}
il int summ(int p){int ret=0;while(p)ret+=tree[p],p-=p&-p;return ret;}
il vd dfs(int now,int gg){
if(gg>=ans)return;
if(s[now].size()==0){ans=gg;return;}
int sum=0;
rep(i,0,s[now].size()-1)if(!summ(dfn[s[now][i]]))++sum;
if(gg+sum-1>=ans)return;
if(sum==1||sum==0){ans=min(ans,gg);return;}
rep(i,0,s[now].size()-1)if(!summ(dfn[s[now][i]])){
add(dfn[s[now][i]],1);
add(dfn[s[now][i]]+siz[s[now][i]],-1);
dfs(now+1,gg+sum-1);
add(dfn[s[now][i]],-1);
add(dfn[s[now][i]]+siz[s[now][i]],1);
}
}
int main(){
freopen(Fname".in","r",stdin);
freopen(Fname".out","w",stdout);
n=gi();
int m=gi(),id=0;
rep(i,1,m){
int a=gi(),b=gi();
nxt[++id]=fir[a],fir[a]=id,dis[id]=b;
nxt[++id]=fir[b],fir[b]=id,dis[id]=a;
}
DFS(1);
dfs(2,1);
printf("%d
",ans);
return 0;
}
没有vector（开O2会吃亏）
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<vector>
#define Fname "epidemic"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=310,maxm=maxn<<1;
int fir[maxn],nxt[maxm],dis[maxm];
int siz[maxn],dfn[maxn],k[maxn],s[maxn][maxn],ans=1e9,n;
il vd DFS(int now,int dep=1,int fa=-1){
s[dep][++k[dep]]=now;
siz[now]=1,dfn[now]=++dfn[0];
erep(i,now)if(dis[i]^fa)DFS(dis[i],dep+1,now),siz[now]+=siz[dis[i]];
}
int tree[maxn];
il vd add(int p,int k){while(p<=n)tree[p]+=k,p+=p&-p;}
il int summ(int p){int ret=0;while(p)ret+=tree[p],p-=p&-p;return ret;}
il vd dfs(int now,int gg){
if(gg>=ans)return;
if(!k[now]){ans=gg;return;}
int sum=0;
rep(i,1,k[now])if(!summ(dfn[s[now][i]]))++sum;
if(gg+sum-1>=ans)return;
if(sum==1||sum==0){ans=min(ans,gg);return;}
rep(i,1,k[now])if(!summ(dfn[s[now][i]])){
add(dfn[s[now][i]],1);
add(dfn[s[now][i]]+siz[s[now][i]],-1);
dfs(now+1,gg+sum-1);
add(dfn[s[now][i]],-1);
add(dfn[s[now][i]]+siz[s[now][i]],1);
}
}
int main(){
freopen(Fname".in","r",stdin);
freopen(Fname".out","w",stdout);
n=gi();
int m=gi(),id=0;
rep(i,1,m){
int a=gi(),b=gi();
nxt[++id]=fir[a],fir[a]=id,dis[id]=b;
nxt[++id]=fir[b],fir[b]=id,dis[id]=a;
}
DFS(1);
dfs(2,1);
printf("%d
",ans);
return 0;
}
给出两组数据
In
15 14
2 1
3 2
4 2
5 2
6 1
7 6
8 6
9 6
10 1
11 10
12 10
13 12
14 10
15 14
Out
8
In
100 99
2 1
3 2
4 3
5 3
6 3
7 2
8 7
9 7
10 9
11 7
12 2
13 12
14 12
15 12
16 2
17 16
18 17
19 17
20 16
21 2
22 21
23 21
24 21
25 1
26 25
27 26
28 25
29 28
30 25
31 30
32 31
33 31
34 31
35 30
36 35
37 35
38 37
39 37
40 1
41 40
42 41
43 41
44 41
45 41
46 40
47 46
48 40
49 40
50 49
51 40
52 51
53 51
54 40
55 54
56 54
57 1
58 57
59 58
60 58
61 58
62 57
63 62
64 62
65 62
66 57
67 66
68 66
69 66
70 66
71 57
72 71
73 71
74 71
75 74
76 57
77 76
78 76
79 76
80 76
81 1
82 81
83 82
84 83
85 82
86 85
87 81
88 87
89 88
90 88
91 87
92 87
93 92
94 92
95 94
96 92
97 96
98 96
99 92
100 99
Out
55