洛谷P1041 传染病控制

解：搜索......

我们可以每次选择分支少的搜索，或者说，贪心的搜索当前更优的决策。

每一层把能剪的点搞出来，按照度数/SIZ排序，然后依次搜索。加个最优化剪枝就完事了。

 #include <bits/stdc++.h>

 const int N = , INF = 0x3f3f3f3f;

 struct Edge {

     int nex, v;

 }edge[N << ]; int tp;

 int e[N], siz[N], in[N], n, ans = INF;

 int v[N][N];

 bool del[N], vis[N];

 inline bool cmp(const int &a, const int &b) {

     //return in[a] > in[b];

     return siz[a] > siz[b];

 }

 inline void add(int x, int y) {

     tp++;

     edge[tp].v = y;

     edge[tp].nex = e[x];

     e[x] = tp;

     return;

 }

 void DFS_1(int x, int f) {

     siz[x] = ;

     for(int i = e[x]; i; i = edge[i].nex) {

         int y = edge[i].v;

         if(y == f) continue;

         DFS_1(y, x);

         siz[x] += siz[y];

     }

     return;

 }

 void DFS(int k, int d) {

     if(k >= ans) return;

     v[d][] = ;

     for(int x = ; x <= n; x++) {

         if(del[x] || !vis[x]) continue;

         /// vis[x]

         for(int i = e[x]; i; i = edge[i].nex) {

             int y = edge[i].v;

             if(vis[y] || del[y]) continue;

             v[d][++v[d][]] = y;

         }

     }

     if(!v[d][]) {

         ans = std::min(ans, k);

         return;

     }

     std::sort(v[d] + , v[d] + v[d][] + , cmp);

     for(int i = ; i <= v[d][]; i++) {

         vis[v[d][i]] = ;

     }

     k += v[d][] - ;

     for(int i = ; i <= v[d][]; i++) {

         int x = v[d][i];

         del[x] = ;

         vis[x] = ;

         DFS(k, d + );

         vis[x] = ;

         del[x] = ;

     }

     for(int i = ; i <= v[d][]; i++) {

         vis[v[d][i]] = ;

     }

     return;

 }

 int main() {

 //    freopen("disease.in", "r", stdin);

 //    freopen("disease.out", "w", stdout);

     int m;

     scanf("%d%d", &n, &m);

     for(int i = , x, y; i <= m; i++) {

         scanf("%d%d", &x, &y);

         add(x, y); add(y, x);

         in[x]++; in[y]++;

     }

     DFS_1(, );

     vis[] = ;

     DFS(, );

     printf("%d\n", ans);

     return ;

 }

AC代码