Warning: session_start(): open(/tmp/sess_e94c3b031a09f1d4d2b720f29278e4d3, 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=2057|POJ 2057]]
//不太聪明的版本//
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
int n,f[1005],sz[1005],head[1005],mxlen[1005],cnt;
bool worm[1005];
struct Node{int nxt,to;}Edges[1005*2];
void addedge(int u,int v)
{
Edges[++cnt].nxt=head[u];
head[u]=cnt,Edges[cnt].to=v;
}
int dfs(int u)
{
if(head[u]==-1){sz[u]=1;return f[u];}
if(f[u])return f[u];
int son[8],top=0,p[8]={0,1,2,3,4,5,6,7};
for(int i=head[u];~i;i=Edges[i].nxt)
{
int v=Edges[i].to;
dfs(v);
sz[u]+=sz[v],son[top++]=v;
}
f[u]=INF;
do
{
int len=0,res=0;
for(int i=0;i0)addedge(f,i);
}
printf("%.4lf\n",1.0*dfs(1)/sz[1]);
}
return 0;
}
//贪心//
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
int n,f[1005],sz[1005],head[1005],mxlen[1005],cnt;
bool worm[1005];
struct Node{int nxt,to;}Edges[1005*2];
void addedge(int u,int v)
{
Edges[++cnt].nxt=head[u];
head[u]=cnt,Edges[cnt].to=v;
}
bool cmp(int x,int y){return (mxlen[x]+2)*sz[y]<(mxlen[y]+2)*sz[x];}
int dfs(int u)
{
if(head[u]==-1){sz[u]=1;return f[u];}
if(f[u])return f[u];
int son[8],top=0;
for(int i=head[u];~i;i=Edges[i].nxt)
{
int v=Edges[i].to;
dfs(v);
sz[u]+=sz[v],son[top++]=v;
mxlen[u]+=mxlen[v]+2;
}
if(worm[u])mxlen[u]=0;
f[u]=0;
sort(son,son+top,cmp);
for(int i=0;i0)addedge(f,i);
}
printf("%.4lf\n",1.0*dfs(1)/sz[1]);
}
return 0;
}