记录编号	441945	评测结果	PPPPPPPPPP
题目名称	[AHOI2008] 上学路线	最终得分	59
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	0.182 s
提交时间	2017-08-25 21:08:34	内存使用	40.56 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=3e5+10;
struct edge{int f,t,g,l,o;}w[N];
int n,m,a[N],b[N],c[N],d[N];
int head[N],next[N],tail[N],cnt;
void add(int f,int t,int g,int l){
	++cnt;w[cnt]=(edge){f,t,g,l,cnt+1};
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	++cnt;w[cnt]=(edge){t,f,0,l,cnt-1};
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
int dis[N];bool inque[N];
queue<int> Q;
void spfa(){
	for (int i=1;i<=n;i++) dis[i]=1e9;
	dis[1]=0;Q.push(1);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		inque[v]=0;
		for (int i=head[v];i;i=next[i])
		if (dis[v]+w[i].l<dis[w[i].t]){
			dis[w[i].t]=dis[v]+w[i].l;
			if (!inque[w[i].t]) inque[w[i].t]=1,Q.push(w[i].t);
		}
	}
}
struct st{int x,i,df;}z[N];
int top,l[N],ans;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	int df=F;ans+=F;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[w[z[i].i].o].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
void bfs(){
	for (int i=1;i<=n;i++) l[i]=0;
	l[1]=1;Q.push(1);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		if (l[n]) continue;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t); 
	}
}
bool dinic(){
	bfs();
	if (!l[n]) return 0;
	z[top=1]=(st){1,head[1],(int)1e9};
	while (top){
		if (V==n){change();top--;E=next[E];}else
		if (!E){l[V]=0;top--;E=next[E];}else
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=(st){w[E].t,head[w[E].t],min(F,w[E].g)},top++;
		else E=next[E]; 
	}
	return 1;
}
int dfn[N],low[N],vis[N],fa[N],stack[N],h;
bool ins[N];
void tarjan(int x){
	static int cnt=0;
	low[x]=dfn[x]=++cnt;
	stack[++h]=x;
	ins[x]=1;
	for (int i=head[x];i;i=next[i])
	if (w[i].g){
		int v=w[i].t;
		if (!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);else
		if (ins[v]) low[x]=min(low[x],dfn[v]);
	}
	if (low[x]==dfn[x]){
		for (;stack[h]!=x;h--)
			fa[stack[h]]=x,ins[stack[h]]=0;
		fa[x]=x;ins[x]=0;h--;
	}
}
int que[N];
int main()
{
	freopen("routez.in","r",stdin);
	freopen("routez.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
		add(a[i],b[i],d[i],c[i]);
	}
	spfa();
	printf("%d\n",dis[n]);
	while (cnt) next[cnt--]=0;
	for (int i=1;i<=n;i++) head[i]=0;
	for (int i=1;i<=m;i++){
		if (dis[a[i]]+c[i]==dis[b[i]]) add(a[i],b[i],d[i],i);
		if (dis[b[i]]+c[i]==dis[a[i]]) add(b[i],a[i],d[i],i);
	}
	while (dinic());
	int K=0;int cost=0;
	bfs();
	for (int i=1;i<=cnt;i+=2)
		if (l[w[i].f]!=0&&l[w[i].t]==0) que[++K]=w[i].l,cost+=d[w[i].l];
	/*tarjan(1);
	for (int v=1;v<=n;v++)
	if (fa[v]==fa[1]){
		for (int i=head[v];i;i=next[i])
		if (!w[i].g&&fa[w[i].t]!=fa[1]) que[++K]=w[i].l,cost+=w[w[i].o].g/2;
	}*/
	printf("%d %d ",K,ans);
	//if (cost!=ans) printf("\nthe cost of these edge is %d\n",cost),puts("FoolMike"),exit(0);
	sort(que+1,que+K+1);
	for (int i=1;i<=K;i++) printf("%d ",que[i]);
	puts("");
	return 0;
}