首先最原始的方法就是不断地枚举要去掉的边~~直到从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;
}