记录编号	9874	评测结果	AAAAAAATTT
题目名称	[AHOI2008] 上学路线	最终得分	70
用户昵称	zqzas	是否通过	未通过
代码语言	C++	运行时间	3.107 s
提交时间	2009-04-21 21:05:32	内存使用	15.92 MiB

#include <iostream>

using namespace std;

#define MAXV 510
#define MAXE 250000
#define INF 999999999

struct Edge{
	int a,b,next;
	int t,c;
	int num;
};

int v,e,ori,ne,fore[MAXV],c[MAXV][MAXV],map[MAXV][MAXV];
long long dis[MAXV][MAXV];
bool vis[MAXV],isinS[MAXV],isinMap[MAXV][MAXV];
struct Edge edge[MAXE],nedge[MAXE];

inline int MIN(int a,int b)
{
	return a<b?a:b;
}

int aug(int x,int min)
{
	if (x==v)
		return min;
	int i,y,inc;
	for (i=1;i<=map[x][0];i++)
	{
		y=map[x][i];
		if (!vis[y] && c[x][y]>0)
		{
			vis[y]=true;
			inc=aug(y,MIN(min,c[x][y]));
			vis[y]=false;
			if (inc>0)
			{
				c[x][y]-=inc;
				c[y][x]+=inc;
				return inc;
			}
		}
	}
	return 0;
}

void bfs(int src)
{
	int i,head,tail,x,y,que[MAXV]={0};
	isinS[src]=true;
	que[0]=src;
	head=-1;
	tail=0;
	while (head<tail)
	{
		x=que[++head];
		for (i=1;i<=map[x][0];i++)
		{
			y=map[x][i];
			if (c[x][y]>0 && !isinS[y])
			{
				isinS[y]=true;
				que[++tail]=y;
			}
		}
	}
}

void output()
{
	int i,x,y,ansc=0,outedge[MAXE]={0};
	for (i=1;i<=ne;i++)
	{
		x=nedge[i].a;
		y=nedge[i].b;
		if (isinS[x] && !isinS[y])
		{
			outedge[++outedge[0]]=nedge[i].num;
			ansc+=nedge[i].c;
		}
	}
	printf("%d\n%d %d\n",ori,outedge[0],ansc);
	for (i=1;i<=outedge[0];i++)
		printf("%d\n",outedge[i]);
}

void maxflow()
{
	int inc,maxf=0;
	while (1)
	{
		memset(vis,0,sizeof(vis));
		vis[1]=true;
		inc=aug(1,INF);
		maxf+=inc;
		if (inc==0)
			break;
	}
	//find cut
	bfs(1);
	output();
}

void dijkstra(int src)
{
	int k,x,y,min,i;
	memset(vis,0,sizeof(vis));
	for (i=1;i<=v;i++)
	{
		dis[src][i]=INF;
	}
	dis[src][src]=0;
	for (k=1;k<=v;k++)
	{
		min=INF;
		for (i=1;i<=v;i++)
			if (!vis[i])
				if (dis[src][i]<min)
				{
					min=dis[src][i];
					x=i;
				}
		vis[x]=true;
		for (i=fore[x];i!=0;i=edge[i].next)
		{
			y=edge[i].b;
			if (!vis[y] && dis[src][x]+edge[i].t<dis[src][y])
				dis[src][y]=dis[src][x]+edge[i].t;
		}
	}
}

void run()
{
	dijkstra(1);
	dijkstra(v);
	ori=dis[1][v];
	int i,a,b,t;
	for (i=1;i<=2*e;i++)
	{
		a=edge[i].a;
		b=edge[i].b;
		t=edge[i].t;
		if (dis[1][a]+dis[v][b]+t==ori)
		{
			nedge[++ne]=edge[i];
			map[b][++map[b][0]]=a;
			map[a][++map[a][0]]=b;
			if (c[a][b]==-1)
				c[a][b]=0;
			c[a][b]+=edge[i].c;
			c[b][a]=0;
		}
	}
	maxflow();
}

inline void addEdge(int &now,int a,int b,int t,int c,int num)
{
	now++;
	edge[now].a=a;
	edge[now].b=b;
	edge[now].t=t;
	edge[now].c=c;
	edge[now].num=num;
	edge[now].next=fore[a];
	fore[a]=now;
}

void ini()
{
	int i,j,a,b,t,C,now=0;
	for (i=0;i<MAXV;i++)
		for (j=0;j<MAXV;j++)
			c[i][j]=-1;
	scanf("%d%d",&v,&e);
	for (i=1;i<=e;i++)
	{
		scanf("%d%d%d%d",&a,&b,&t,&C);
		addEdge(now,a,b,t,C,i);
		addEdge(now,b,a,t,C,i);
	}
}

int main()
{
	freopen("routez.in","r",stdin);
	freopen("routez.out","w",stdout);
	ini();
	run();
	return 0;
}