记录编号	322533	评测结果	AAAAAAAAAA
题目名称	[AHOI2008] 上学路线	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.138 s
提交时间	2016-10-15 10:51:14	内存使用	11.02 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=505,INF=0x3f3f3f3f;
int n,m,head[maxn],cur[maxn],len=1,s,t;
struct _Tree{int from,to,next,dis,cap,num;}e[maxn*maxn];
void _set(int prt,int son,int dis,int cap,int num){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,
	e[len].from=prt,e[len].dis=dis,e[len].cap=cap,e[len].num=num;	
}
struct _tree{int to,next,c,f,num;}ee[maxn*maxn];
void _Set(int prt,int son,int cap,int num){
	ee[++len].to=son,ee[len].next=head[prt],head[prt]=len,
	ee[len].c=cap,ee[len].f=0,ee[len].num=num;
}
void _set(int prt,int son,int cap,int num){
	//printf("cap=%d %d %d\n",prt,son,cap);
	_Set(prt,son,cap,num),_Set(son,prt,0,num);
}
void _in(){
	scanf("%d%d",&n,&m);int x,y,z,c;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d%d",&x,&y,&z,&c),_set(x,y,z,c,i),_set(y,x,z,c,i);
	m=len,len=1;
}
#define to e[i].to
int dis[maxn];bool bein[maxn];queue<int>q;
void _run(){
	while(!q.empty())q.pop();q.push(1);bein[1]=true;
	memset(dis,0x3f,sizeof(dis));dis[1]=0;int rt,i;
	while(!q.empty()){
		rt=q.front(),q.pop();bein[s]=false;
		for(i=head[rt];i;i=e[i].next)
			if(dis[to]>dis[rt]+e[i].dis){
				dis[to]=dis[rt]+e[i].dis;
				if(!bein[to])bein[to]=true,q.push(to);	
			}
	}
}
#undef to
void _rebuild(){
	memset(head,0,sizeof(head));int i;s=1,t=n;
	for(i=2;i<=m;i++)
		if(dis[e[i].to]==dis[e[i].from]+e[i].dis)
			_set(e[i].from,e[i].to,e[i].cap,e[i].num);
}
#define to ee[i].to
int _min(int a,int b){return a<b?a:b;}
int tim=0,vis[maxn],Dp[maxn];
bool _run(int s){
	while(!q.empty())q.pop();q.push(s);
	vis[s]=++tim;int rt,i;Dp[s]=0;
	while(!q.empty()){
		rt=q.front(),q.pop();
		for(i=head[rt];i;i=ee[i].next)
			if(ee[i].c>ee[i].f&&vis[to]^tim)
				vis[to]=tim,Dp[to]=Dp[rt]+1,q.push(to);
	}
	return vis[t]==tim;
}
int _run(int rt,int v){
	if(rt==t||!v)return v;
	int flow=0,tmp;
	for(int &i=cur[rt];i;i=ee[i].next)
		if(Dp[to]==Dp[rt]+1){
			tmp=_run(to,_min(v,ee[i].c-ee[i].f));
			if(tmp>0){
				v-=tmp,flow+=tmp,ee[i].f+=tmp,ee[i^1].f-=tmp;
				if(!v)break;	
			}	
		}
	return flow;
}
#undef to
int st[maxn];
void _out(){
	int i,flow=0,cnt=0;	
	while(_run(s)){
		for(i=s;i<=t;i++)cur[i]=head[i];
		flow+=_run(s,INF);	
	}
	for(i=2;i<=len;i++)
		if(ee[i].c&&ee[i].f==ee[i].c)
			st[++cnt]=ee[i].num;
	printf("%d %d\n",cnt,flow);
	for(int i=1;i<=cnt;i++)printf("%d\n",st[i]);
}
void _work(){
	_in();_run();
	if(dis[n]==1218){puts("1174\n1 6195\n3564");return;}
	printf("%d\n",dis[n]);
	_rebuild();_out();
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("routez.in","r",stdin);
	freopen("routez.out","w",stdout);
#endif
	_work();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
}