USACO Section 4.4 Pollutant Control - 找更优的搜索枚举方案~

首先最原始的方法就是不断地枚举要去掉的边~~直到从1出发到不了N...中间可以用个优化...若所去掉的边代价和大于前面找到的解..那么就剪掉...开始我确实这么写了..前几个没错..但效率很捉急啊....

再在这个方向想...因为每次去掉一条边后..都要从起点开始进行此搜索..能到达终点才继续往下搜..何不把这个搜索过程利用起来...于是我就把每次搜索找到的路径记录下来...而去掉的边总是这些路径上的边...因为这条路经去掉了这一条边肯定是不通了...这样可以减去很多根本不需要去尝试去掉的边...但效率依然不够满意..

最后我就想到了记录路径不是记录边..而是记录点...每次搜索记录下的路径是一条可行的从1~N顺序经过的点..而每次枚举是枚举这条路经上是去掉哪个点...选择了去掉某个点..就将这个路径上(此点前面的所有点)到此点的边都标记为不可使用..并将这些标记了的边以及去掉它们的代价和都记录下来...那么就相当于把这个点从路径中去掉了...因为大多数情况..以这种方法找路径后去掉的边不止一条~~甚至一次砍几百条边..效率很高啊..果断就过了...

Program:

/* ID: zzyzzy12 LANG: C++ TASK: milk6 */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<map> #include<algorithm> #include<queue> #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; struct node { int x,y,c,next; }line[1005]; int n,m,_link[35],waynum,way[35]; int Now[1005],len,TempNow[1005]; int ansnum,ansdata,ans[1005]; bool used[45],f[1005]; bool findway(int p) { int k; way[++waynum]=p; used[p]=true; if (p==n) return true; k=_link[p]; while (k) { if (f[k] && !used[line[k].y]) if (findway(line[k].y)) return true; k=line[k].next; } waynum--; used[p]=false; return false; } void findanswer(int data) { int NowWay[1005],NowNum,i,k,p,TempData; int CutLine[1005],CutNum; if (data>ansdata) return; memset(used,false,sizeof(used)); waynum=0; if (findway(1)) { NowNum=waynum; for (i=1;i<=NowNum;i++) NowWay[i]=way[i]; for (i=2;i<=NowNum;i++) { CutNum=0; TempData=0; for (p=1;p<i;p++) { k=_link[NowWay[p]]; while (k) { if (f[k] && line[k].y==NowWay[i]) { f[k]=false; Now[++len]=k; CutLine[++CutNum]=k; TempData+=line[k].c; if (TempData+data>ansdata) goto A; } k=line[k].next; } } findanswer(data+TempData); A: ; len-=CutNum; for (k=1;k<=CutNum;k++) f[CutLine[k]]=true; } }else { for (i=1;i<=len;i++) TempNow[i]=Now[i]; sort(TempNow+1,TempNow+1+len); if (ansdata>data) { ansdata=data; ansnum=len; for (i=1;i<=len;i++) ans[i]=TempNow[i]; }else { if (ansnum<len) return; if (ansnum==len) for (i=1;i<=len;i++) if (ans[i]>TempNow[i]) break; else if (ans[i]<TempNow[i]) return; ansnum=len; for (i=1;i<=len;i++) ans[i]=TempNow[i]; } } return; } int main() { freopen("milk6.in","r",stdin); freopen("milk6.out","w",stdout); int i; scanf("%d%d",&n,&m); memset(_link,0,sizeof(_link)); for (i=1;i<=m;i++) { scanf("%d%d%d",&line[i].x,&line[i].y,&line[i].c); line[i].next=_link[line[i].x]; _link[line[i].x]=i; } memset(f,true,sizeof(f)); ansdata=oo; ansnum=0; len=0; findanswer(0); printf("%d %d\n",ansdata,ansnum); for (i=1;i<=ansnum;i++) printf("%d\n",ans[i]); return 0; }