 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求数据！！！！求数据！！！！因为这道题都说输入有问题，所以我也构造不出来什么好的数据，只能在这里求数据了。
我先贴一下我的RE代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 205
using namespace std;
struct Syndra
{
int v,next;
}e[N*N];
int head[N],cnt;
void add(int u,int v)
{
cnt++;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int n,m,ans,num[N],w[N];
int resp[N],d[N],visit[N];
char coco[N][N];
char respect[N][N][N];
char tem[N];
int f[N][N];
void dfs(int x)
{
num[x]=0;
int i,j,k,v;
for(i=1;i<=n;i++)f[x][i]=w[x];
for(i=head[x];i;i=e[i].next)
{
v=e[i].v;
dfs(v);
for(j=num[x]+num[v];j;j--)
{
int uplimit=min(num[v],j);
for(k=max(j-num[x],0);k<=uplimit;k++)
{
f[x][j]=min(f[x][j],f[x][j-k]+f[v][k]);
}
}
num[x]+=num[v];
}
num[x]++;
return ;
}
int main()
{
// freopen("test.in","r",stdin);
int i,j,k;
while(1)
{
scanf("%s",tem);
if(tem[0]=='#')break;
n=tem[0]-'0';
scanf("%d",&m);
for(i=1;i<=n;i++)
{
scanf("%s%d",coco[i],&w[i]);
resp[i]=d[i]=0;
while(tem[0]=getchar(),tem[0]!='\n')
{
if(tem[0]==' '||tem[0]==' '||tem[0]=='\r')continue;
else respect[i][++resp[i]][0]=tem[0],scanf("%s",respect[i][resp[i]]+1);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=resp[i];j++)
{
for(k=1;k<=n&&strcmp(coco[k],respect[i][j]);k++);
add(i,k);
d[j]++;
}
}
for(i=1;i<=n;i++)if(!d[i])add(0,i);
w[0]=99999999;
dfs(0);
for(ans=99999999,i=m;i<=n;i++)ans=min(ans,f[0][i]);
printf("%d\n",ans);
}
return 0;
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
