我要评论洛谷 p3959 [noip2017 提高组] 宝藏
题目链接洛谷 p3959 [noip2017 提高组] 宝藏
题目大意
一道奇奇怪怪的类似生成树的题目。
半正解 （过不了 h a c k hack hack ）
用 d f s + dfs+ dfs+贪心优化。（ w a wa wa 了两个点，因为贪心正确性有点…）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int bignum=1e17;
const int maxn=1000;
const int maxm=4000;
const int maxf=50100;
int hd[maxm],nxt[maxm],to[maxm],l[maxm],bz[maxn],vis[maxn],dep[maxn],fnn[maxn],id[maxn],s[maxf];
int n,m,cnt,top,ans=bignum,maxn;
inline int mymin(int a,int b)
{
return a<b?a:b;
}
void add(int u,int v,int vl)
{
nxt[++cnt]=hd[u];
hd[u]=cnt;
to[cnt]=v;
l[cnt]=vl;
nxt[++cnt]=hd[v];
hd[v]=cnt;
to[cnt]=u;
l[cnt]=vl;
}
void qsort(int l,int r)
{
int i=l,j=r,mid=fnn[((l+r)>>1)+1];
while(i<=j)
{
while(fnn[i]>mid)i++;
while(fnn[j]<mid)j--;
if(i<=j)
{
int op=fnn[i];
fnn[i]=fnn[j];
fnn[j]=op;
op=id[i];
id[i]=id[j];
id[j]=op;
i++,j--;
}
}
if(l<j)qsort(l,j);
if(i<r)qsort(i,r);
}
void dfs(int p,int sum,int fnn)
{
// cout<<p<<endl;
if(sum>ans) return ;
if(p==n)
{
ans=mymin(ans,sum);
return ;
}
for(int i=1;i<=top;i++)
{
if(sum>ans) return ;
for(int j=hd[vis[i]];j;j=nxt[j])
{
// if(sum>ans) return ;
if(sum+(dep[vis[i]]+1)*l[j]>ans) continue ;
// printf("%lld %lld\n",fnn[to[j]],ss*l[j]);
if(bz[to[j]]==0&&s[fnn+(1<<to[j])]>sum+(dep[vis[i]]+1)*l[j])
{
bz[to[j]]=1;
vis[++top]=to[j];
dep[to[j]]=dep[vis[i]]+1;
s[fnn+(1<<to[j])]=sum+dep[to[j]]*l[j];
// fnn[to[j]][dep[vis[i]+1]]=(dep[vis[i]]+1)*l[j];
dfs(p+1,sum+dep[to[j]]*l[j],fnn+(1<<to[j]));
vis[top]=0;
top--;
dep[to[j]]=0;
bz[to[j]]=0;
}
// else maxn=min(maxn,s[fnn+(1<<to[j])]);
}
}
}
signed main()
{
// freopen("treasure.in","r",stdin);
// freopen("treasure.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) id[i]=i;
for(int i=1;i<=m;i++)
{
int u,v,vl;
scanf("%lld%lld%lld",&u,&v,&vl);
if(u!=v)
{
add(u,v,vl);
}
}
qsort(1,n);
for(int i=1;i<=n;i++)
{
for(int j=0;j<=50000;j++) s[j]=bignum;
top=0;
// s[(1<<id[i])]=0;
vis[++top]=id[i];
bz[id[i]]=1;
dfs(1,0,(1<<id[i]));
bz[id[i]]=0;
}
// cout<<maxn<<endl;
printf("%lld",ans);
return 0;
}
正解
神犇都用
d
p
dp
dp ，我用
d
f
s
+
dfs+
dfs+状压优化。
当选了哪几个点时，将其压缩，放入数组，然后跑
d
f
s
dfs
dfs 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e16;
const int maxn=1100;
int vis[maxn],l[maxn],d[maxn];
int c[maxn][maxn],to[maxn][maxn];
int ans=inf,tmp,tot,cnt,n,m,sum;
void qsort(int l,int r,int p)
{
int i=l,j=r,mid=c[p][to[p][(l+r)/2+1]];
while(i<=j)
{
while(c[p][to[p][i]]<mid)i++;
while(c[p][to[p][j]]>mid)j--;
if(i<=j)
{
swap(to[p][i],to[p][j]);
// swap(c[p][to[p][i]],c[p][to[p][j]]);
i++,j--;
}
}
if(l<j)qsort(l,j,p);
if(i<r)qsort(i,r,p);
}
void dfs(int num,int node)
{
for(int i=num;i<=sum;i++)
{
if(tot+cnt*l[vis[i]]>=ans) return;
for(int j=node;j<=d[vis[i]];j++)
if(!l[to[vis[i]][j]])
{
sum++;
vis[sum]=to[vis[i]][j];
cnt-=c[vis[sum]][to[vis[sum]][1]];
tot+=c[vis[i]][vis[sum]]*l[vis[i]];
l[vis[sum]]=l[vis[i]]+1;
dfs(i,j+1);
tot-=c[vis[i]][vis[sum]]*l[vis[i]];
l[vis[sum]]=0;
cnt+=c[vis[sum]][to[vis[sum]][1]];
sum--;
}
node=1;
}
if(sum==n)
{
if(tot<ans) ans=tot;
return;
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
c[i][j]=inf;
}
}
for(int i=1;i<=m;i++)
{
int u,v,vl;
scanf("%lld%lld%lld",&u,&v,&vl);
if(c[u][v]<vl) continue ;
if(c[u][v]==inf) to[u][++d[u]]=v,to[v][++d[v]]=u;
c[u][v]=c[v][u]=vl;
}
for(int i=1;i<=n;i++)
{
qsort(1,d[i],i);
cnt+=c[i][to[i][1]];
}
for(int i=1;i<=n;i++)
{
tot=0,sum=1;
vis[1]=i;
cnt-=c[i][to[i][1]];
l[i]=1;
dfs(1, 1);
l[i]=0;
cnt+=c[i][to[i][1]];
}
printf("%lld",ans);
return 0;
}
发表评论