记录编号	362577	评测结果	AAAAAAAAAA
题目名称	[AHOI2008] 上学路线	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.216 s
提交时间	2017-01-07 19:27:47	内存使用	4.27 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=510,maxe=125010;
struct edge{int to,cap,prev,id;}e[maxe<<1];
void SPFA();
void addedge(int,int,int,int);
void AddEdge(int,int,int,int);
int Dinic();
void bfs();
int dfs(int,int);
void dfs(int);
vector<int>G[maxn],W[maxn],C[maxn],id[maxn];
int last[maxn],len=0,d[maxn],cur[maxn];
bool inq[maxn]={false},vis[maxn]={false},ans[maxe]={false};
int n,m,s,t,x,y,z,w,tmp=0,cnt=0;
int main(){
	freopen("routez.in","r",stdin);
	freopen("routez.out","w",stdout);
	memset(last,-1,sizeof(last));
	scanf("%d%d",&n,&m);
	s=1;t=n;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&x,&y,&z,&w);
		G[x].push_back(y);
		W[x].push_back(z);
		C[x].push_back(w);
		id[x].push_back(i);
		G[y].push_back(x);
		W[y].push_back(z);
		C[y].push_back(w);
		id[y].push_back(i);
	}
	SPFA();
	printf("%d\n",d[t]);
	for(x=1;x<=n;x++)for(int i=0;i<(int)G[x].size();i++)if(d[x]+W[x][i]==d[G[x][i]])addedge(x,G[x][i],C[x][i],id[x][i]);
	tmp=Dinic();
	dfs(s);
	for(x=1;x<=n;x++)for(int i=last[x];i!=-1;i=e[i].prev)if(!e[i].cap&&vis[x]&&!vis[e[i].to]){
		cnt++;
		ans[e[i].id]=true;
	}
	printf("%d %d\n",cnt,tmp);
	for(int i=1;i<=m;i++)if(ans[i])printf("%d\n",i);
	return 0;
}
void SPFA(){
	int x;
	fill(d+1,d+n+1,0x3f3f3f3f);
	queue<int>q;
	q.push(s);
	d[s]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		inq[x]=false;
		for(int i=0;i<(int)G[x].size();i++)if(d[G[x][i]]>d[x]+W[x][i]){
			d[G[x][i]]=d[x]+W[x][i];
			if(!inq[G[x][i]]){
				inq[G[x][i]]=true;
				q.push(G[x][i]);
			}
		}
	}
}
void addedge(int x,int y,int z,int i){
	AddEdge(x,y,z,i);
	AddEdge(y,x,0,i);
}
void AddEdge(int x,int y,int z,int i){
	e[len].to=y;
	e[len].cap=z;
	e[len].id=i;
	e[len].prev=last[x];
	last[x]=len++;
}
int Dinic(){
	int flow=0;
	while(bfs(),d[t]!=-1){
		copy(last+1,last+n+1,cur+1);
		flow+=dfs(s,(~0u)>>1);
	}
	return flow;
}
void bfs(){
	int x;
	queue<int>q;
	fill(d+1,d+n+1,-1);
	q.push(s);
	d[s]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]==-1){
			d[e[i].to]=d[x]+1;
			q.push(e[i].to);
		}
	}
}
int dfs(int x,int delta){
	if(x==t||!delta)return delta;
	int flow=0,f;
	for(int i=last[x];delta&&i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]==d[x]+1&&(f=dfs(e[i].to,min(delta,e[i].cap)))){
		e[i].cap-=f;
		e[i^1].cap+=f;
		flow+=f;
		delta-=f;
	}
	return flow;
}
void dfs(int x){
	vis[x]=true;
	for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&!vis[e[i].to])dfs(e[i].to);
}