Warning: session_start(): open(/tmp/sess_f22e24174e746324b8e802592b05539d, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
[[http://poj.org/problem?id=1947|POJ 1947]]
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
int n,p,res,head[155],cnt,f[155][155];
struct Node{int nxt,to;}Edges[155*2];
void addedge(int u,int v)
{
Edges[++cnt].nxt=head[u];
head[u]=cnt,Edges[cnt].to=v;
}
void dfs(int u)
{
f[u][1]=0;
for(int i=head[u];~i;i=Edges[i].nxt)
{
int v=Edges[i].to;
if(f[v][1]!=INF)continue;
dfs(v);
for(int j=p;j;j--)
{
f[u][j]=f[u][j]+1;
for(int k=0;k<=j;k++)
{
f[u][j]=min(f[u][j],f[v][k]+f[u][j-k]);
}
}
}
if(u!=1)res=min(res,f[u][p]+1);
else res=min(res,f[u][p]);
}
int main()
{
while(~scanf("%d%d",&n,&p))
{
cnt=0,res=INF;
memset(head,-1,sizeof(head));
memset(f,0x3f,sizeof(f));
for(int i=1;i