注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

有一种力量  

2009-07-20 21:41:05|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
有一道题,没做过绝对不会知道什么叫强剪枝。
有一种力量,没用过绝对不会知道什么叫“王道”

有一种力量,黑夜中霹雳出惊雷。
有一种力量,泥泞中诞生出奇迹。

它,叫暴力!

一个树网,求一个长度不超过K的路径,使边权和最大。
N<=30000

正规做法:分治
断开一个边,分成两个子图,用dfs+sort+merge处理所有经过这个边的路径,然后分治。
断边的选择:选择点数最接近总点数/2的子树,把它的根和原图分离
代码见Code1
复杂度Ω(nlognlogn)

如何进行优化?
用基数排序!
复杂度Ω(nlogn)

还能怎么优化?

用暴力!
暴力枚举起点,用dfs枚举终点,外加
┌─┐──┐┌─┴─┴┐┌╮┌┼─┐
  │─┬┘┌──┐┐┐┌┼┌┴─┐
┌─┘─┼┐├──┤││╭┤│  │
└─┐─┼┘└──┤│││││  │
╭ │ ││└─┬──┐│├╰─╮╯
└─╯─┴┤└─╯└─╯└└└╯└╯
强剪枝!
记录一个点从一条边走过后最大还可以得到的收益maxV(忽略K的限制),与相应的代价maxL。
1.
if cur+maxV<bestResult return;
2.
if cur+maxL<=K
    if (cur+maxV>bestResult)bestResult=cur+maxV
    return
实践证明:
只用第一个剪枝,AC
只用第二个剪枝:AC
用第一+二个剪枝,AC,且比标程(DC)快

为什么?
如果K很小,那么dfs时一共不会遇到多少个点
如果K很大,那么统统被剪枝2剪掉了

所以,人间正道是暴力!
暴力枚举,暴力剪枝,暴力AC!

当山穷水尽的时候,用暴力打开通向柳暗花明的道路。
当深陷泥潭的时候,用暴力破除WA+RE+TLE的噩梦。
当无可奈何时,用暴力。
当无计可施时,用暴力。
当心情黯淡时,用暴力。
用暴力总会有奇迹!

代码见Code2


//Code1
#include <cstdio>
#define NMax 30000
using namespace std;
struct edge{
int e,c,v;edge *next;
}epool[NMax<<1];
struct data{
int c,v;
};
edge *E[NMax];
int etop;
int N,K,bestr;
int color[NMax],cc;
data *lst,L1[NMax],L2[NMax],*lst2;
int lc1,lc2;
int bestK,bestR,nc,bestV,bestF,bestC;
int Abs(int a){return a<0?-a:a;}
int dfs_center(int id,int fa,int cl,int v,int c){
int ret;ret=1;
for (edge *p=E[id];p;p=p->next)if (p->e!=fa && color[p->e]==cl)ret+=dfs_center(p->e,id,cl,p->v,p->c);
if (fa!=-1 && Abs(nc-ret-ret)<=Abs(nc-bestR-bestR)){
bestK=id;bestF=fa;bestV=v;bestR=ret;bestC=c;
}
return ret;
}
void dfs_color(int id,int fa,int cl,int cl2){
color[id]=cl2;
for (edge *p=E[id];p;p=p->next)if (p->e!=fa && color[p->e]==cl)dfs_color(p->e,id,cl,cl2);
}
void dfs_distance(int id,int fa,int cl,int dis,int v){
lst[nc].c=dis;lst[nc].v=v;nc++;
for (edge *p=E[id];p;p=p->next)if (p->e!=fa && p->c+dis<=K && color[p->e]==cl){
dfs_distance(p->e,id,cl,dis+p->c,v+p->v);
}
}
void Qsort(int b,int e){if (b>=e)return;
data t;
int j;
t=lst[b];lst[b]=lst[(b+e)>>1];lst[(b+e)>>1]=t;
for (int i=j=b+1;i<=e;i++)if (lst[b].c>lst[i].c ||
lst[b].c==lst[i].c && lst[b].v<lst[i].v){
t=lst[i];lst[i]=lst[j];lst[j]=t;
j++;
}
--j;
t=lst[b];lst[b]=lst[j];lst[j]=t;
Qsort(b,j-1);Qsort(j+1,e);
}
void dfs(int id,int cl,int ns){
if (ns==1){
lst[0].c=0;lst[0].v=0;lc1=1;
return;
}
nc=ns;
bestK=0;bestR=ns;
dfs_center(id,-1,cl,0,0);
cc++;
int br,bk,bf,bv,bc,bcc;
br=bestR;bk=bestK;bf=bestF;bv=bestV;bc=bestC;
bcc=cc;
data *tmp,dtmp;
int j;
dfs_color(bk,bf,cl,cc);
nc=0;
dfs_distance(bk,bf,bcc,0,0);
Qsort(0,nc-1);
lc1=nc;
lc1=0;
for (int i=0;i<nc;i++){
if (!lc1 || lst[i].v>lst[lc1-1].v){
if (lc1!=i){
dtmp=lst[i];lst[i]=lst[lc1];lst[lc1]=dtmp;
}
lc1++;
}
}
tmp=lst;lst=lst2;lst2=tmp;lc2=lc1;
nc=0;
dfs_distance(bf,bk,cl,0,0);
lc1=nc;
Qsort(0,nc-1);
lc1=0;
for (int i=0;i<nc;i++){
if (!lc1 || lst[i].v>lst[lc1-1].v){
if (lc1!=i){
dtmp=lst[i];lst[i]=lst[lc1];lst[lc1]=dtmp;
}
lc1++;
}
}
j=lc2-1;
for (int i=0;i<lc1;i++){
while (j>=0 && bc+lst[i].c+lst2[j].c>K)j--;
if (j>=0)if (lst[i].v+bv+lst2[j].v>bestr)bestr=lst[i].v+bv+lst2[j].v;
}
dfs(bk,cc,br);
dfs(bf,cl,ns-br);
dfs_color(bk,bf,bcc,cl);
}
int DividAndConquer(){
cc=0;bestr=0;
for (int i=0;i<N;i++)color[i]=0;
lst=L1;lst2=L2;
dfs(0,0,N);
return bestr;
}
int main()
{
edge *p;
int M,x,y,c,v;
etop=0;
FILE *fin,*fout;
fin=fopen("travel.in","r");fout=fopen("travel.out","w");
fscanf(fin,"%d %d %d",&N,&M,&K);
for (int i=0;i<N;i++)E[i]=NULL;
for (int i=0;i<M;i++){
fscanf(fin,"%d %d %d %d",&x,&y,&c,&v);x--;y--;
p=epool+(etop++);
p->next=E[x];p->e=y;p->c=c;p->v=v;
E[x]=p;
p=epool+(etop++);
p->next=E[y];p->e=x;p->c=c;p->v=v;
E[y]=p;
}
fprintf(fout,"%d\n",DividAndConquer());
fclose(fin);fclose(fout);
return 0;
}

//Code2
#include <cstdio>
#define NMax 30000
using namespace std;
struct edge{
int e,c,v;edge *next;
int mV,mL;
edge(){mV=-1;}
}epool[NMax<<1];
edge *E[NMax];
int etop;
int N,K,goodr,bestr;
void compute(edge *a,int f){
a->mV=a->mL=0;
for (edge *p=E[a->e];p;p=p->next)if (p->e!=f){
if (p->mV==-1)compute(p,a->e);
if (p->mV+p->v>a->mV){
a->mV=p->mV+p->v;
a->mL=p->mL+p->c;
}
}
}
void dfs(int id,int fa,int cst,int hap){
if (hap>goodr)goodr=hap;
edge *p;
for (p=E[id];p;p=p->next)if (p->e!=fa && cst+p->c<=K){
if (p->mV==-1)compute(p,id);
if (p->v+p->mV+hap<=bestr)continue;
if (p->mL+p->c+cst<=K){
if (p->mV+hap+p->v>bestr)
bestr=p->mV+hap+p->v;
}else dfs(p->e,id,cst+p->c,hap+p->v);
}
}
int BruteForce(){
bestr=0;
for (int i=0;i<N;i++){
goodr=0;
dfs(i,-1,0,0);
if (bestr<goodr)bestr=goodr;
}
return bestr;
}
int main()
{
edge *p;
int M,x,y,c,v;
etop=0;
FILE *fin,*fout;
fin=fopen("travel.in","r");fout=fopen("travel.out","w");
fscanf(fin,"%d %d %d",&N,&M,&K);
for (int i=0;i<N;i++)E[i]=NULL;
for (int i=0;i<M;i++){
fscanf(fin,"%d %d %d %d",&x,&y,&c,&v);x--;y--;
p=epool+(etop++);
p->next=E[x];p->e=y;p->c=c;p->v=v;
E[x]=p;
p=epool+(etop++);
p->next=E[y];p->e=x;p->c=c;p->v=v;
E[y]=p;
}
fprintf(fout,"%d\n",BruteForce());
fclose(fin);fclose(fout);
//getchar();
return 0;
}

  评论这张
 
阅读(604)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017