同求
三十分,WA&TLE
楼主有头绪了吗？
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 310,MAXP = 310;
#define DEBUG(x) cout<< #x <<":"<< x <<endl
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')w=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*w;
}
int n,p;
int first[MAXN],f[MAXN];
vector<int> node[MAXP];
struct edge{
int u,v,w,next;
//edge(int u,int v,int w=1,int next):u(u),v(v),w(w),next(next){}
}e[MAXP*2];
int tot=0;
void insert(int u,int v){
e[++tot].u=u;e[tot].v=v;e[tot].w=1;e[tot].next=first[u];first[u]=tot;
}
int fa[MAXN],d[MAXN],deep=0;
void init(int x,int fat){
if(x!=1){
d[x]=d[fat]+1;
fa[x]=fat;
}
deep=max(d[x],deep);
node[d[x]].push_back(x);
for(int i=first[x];i!=-1;i=e[i].next){
if(e[i].v!=fat){
init(e[i].v,x);
}
}
}
int find(int x){//找点x和他祖先是否被阻断过，是返回0(不可以感染)
while(x!=1){
for(int i=first[x];i!=-1;i=e[i].next)
if(e[i].v==fa[i]){
if(e[i].w==0)return 0;
break;
}
x=fa[x];
}
return 1;
}
int kill(int x){//返回杀死了多少人
int tot=0;
for(int i=0;i<node[x].size();i++){
for(int j=first[node[x][i]];j!=-1;j=e[j].next){
if(e[j].v==fa[node[x][i]]&&e[j].w&&find(node[x][i])){
tot++;
}
}
}
return tot;
}
int ans=2147483647;
void solve(int x,int o){
if(x==deep+1){
ans=min(ans,o);
return;
}
if(o>=ans)return;
for(int i=0;i<node[x].size();i++){
for(int j=first[node[x][i]];j!=-1;j=e[j].next){
if(e[j].v==fa[node[x][i]]){
e[j].w=0;
int ki=kill(x);
solve(x+1,o+ki);
e[j].w=1;
}
}
}
}
int main(){
memset(first,-1,sizeof(first));
n=read();p=read();
for(int i=1;i<=p;i++){
int u=read(),v=read();
insert(u,v);insert(v,u);
}
d[1]=0;
init(1,-1);
solve(1,1);
printf("%d\n",ans);
return 0;
}
```
by Dark_Van @ 2019-02-19 17:27:29
30分
#include<bits/stdc++.h>
using namespace std;
int n,p,sum[310],ans,c[310],w[310][310],vis[310],h[310],cnt;
int main()
{
scanf("%d%d",&n,&p);
c[1]=1;
for(int i=1;i<=p;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(a>b)swap(a,b);
sum[a]++;
w[a][b]=1;
c[b]=c[a]+1;
}
for(int i=2;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(w[i][j]==1)
sum[i]+=sum[j];
}
}
for(int i=2;i<=n;i++)sum[i]+=1;
for(int i=2;i<=c[n];i++)
{
int maxx=0,num=0;
for(int j=2;j<=n;j++)
{
if(c[j]==i&&vis[j]==0)
if(maxx<sum[j])
{
maxx=sum[j];
num=j;
}
}
vis[num]=1;
for(int l=num+1;l<=n;l++)
if(w[num][l])vis[l]==1;
ans+=maxx;
}
printf("%d",n-ans);
return 0;
}
by IOI_AKer_yyh @ 2019-03-24 14:56:26
30分 同求！
~~~cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
int nxt , to;
}e[10100];
int n , m , siz[10100] , dep[10100] , res[10100][301] , cnt , head[10100] , ans = 2147483647;
bool off[10100];
void add(int from,int to)
{
e[++cnt].to = to;
e[cnt].nxt = head[from];
head[from] = cnt;
}
void dfs(int root,int step)
{
siz[root] = 1;
dep[root] = step;
res[step][++res[step][0]] = root;
if(!head[root]) return;
for(int i = head[root];i;i = e[i].nxt)
{
dfs(e[i].to,step+1);
siz[root] += siz[e[i].to];
}
}
void fuck(int x)
{
off[x] = 1;
for(int i = head[x];i;i = e[i].nxt) fuck(e[i].to);
}
void refuck(int x)
{
off[x] = 0;
for(int i = head[x];i;i = e[i].nxt) refuck(e[i].to);
}
void search(int step,int now)
{
for(int i = 1;i <= res[step+1][0];i ++)
{
int to = res[step+1][i];
if(off[to]) continue;
fuck(to);
search(step+1,now-siz[to]);
refuck(to);
}
ans = min(ans,now);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1 , x , y , z;i <= m;i ++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
dfs(1,1);
search(1,n);
printf("%d\n",ans);
return 0;
}
~~~
by Treaker @ 2019-06-14 11:17:23