【NOIP 2003向上群T 4】伝染病コントロール-DFS剪定
1128 ワード
テストアドレス:伝染病コントロール
作り方:層別DFS.現在のレイヤの候補点に1つの点を列挙するたびに、サブツリーを切り捨て、検索を続け、最小値を探せばいいです.
以下は本人コードです.
作り方:層別DFS.現在のレイヤの候補点に1つの点を列挙するたびに、サブツリーを切り捨て、検索を続け、最小値を探せばいいです.
以下は本人コードです.
#include
#include
#include
#include
#include
#include
#define inf 2000000000
using namespace std;
int n,p,tot=0,first[310]={0},f[310]={0};
struct edge {int v,next;} e[610];
vector G[310];
void insert(int a,int b)
{
e[++tot].v=b;
e[tot].next=first[a];
first[a]=tot;
}
void DFS(int v,int f)
{
for(int i=first[v];i;i=e[i].next)
if (e[i].v!=f)
{
G[v].push_back(e[i].v);
DFS(e[i].v,v);
}
}
int dfs(const vector &state) // ， ，
{
int len=state.size();
if (!len) return 0;
int ans=inf; //ans
vector next;
for(int i=0;i a;
for(unsigned int i=0;i