有n个人，有k个人可以选作传播疾病的母体，和病人直接接触的未被感染者会被感染，求出选择k个人中的哪个可以取得最多的病人数目，有相同的取编号小的那个。
简单搜索，剪枝是如果一个同为母体的可以被其他母体直接或间接传染，这个母体就肯定不会是最多的那个，只会是一条分支。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define PI acos(-1.0) #define MAXN 10100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct node{ int v,next; }edge[250000]; int head[5010],a[5010],vis[5010]; int num[5100]; int cnt,ans,maxm,sum; void add_edge(int u,int v){ edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++; } int dfs(int u){ int i,j; int sum=1; vis[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(num[v]) { num[v]=0; } if(!vis[v]) { sum+=dfs(v); } } return sum; } int main(){ char c; int n,i,j,x,t,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(num,0,sizeof(num)); memset(head,-1,sizeof(head)); cnt = 0; maxm=0; for(i=0;i maxm){ maxm = sum; ans = a[i]; } } } printf("%d\n",ans); } return 0; }