记录编号	37932	评测结果	APPPAAPEEE
题目名称	[AHOI2008] 上学路线	最终得分	54
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	0.352 s
提交时间	2012-04-10 12:55:31	内存使用	0.35 MiB

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int INF=~0U>>2;
const int MAXN=501;
typedef vector<int> VEC;
typedef int Array[MAXN];
int N,M,S,T; Array dist1,dist2,flag;
VEC Map[MAXN],Val[MAXN],Cost[MAXN],Num[MAXN];

queue<int>Q;
void SPFA(int start,int end,Array& dist)
{
	S=start,T=end;
    for(int i=1;i<=N;i++) dist[i]=INF,flag[i]=0;
    dist[S]=0;  Q.push(S); flag[S]=1;
    int u,v,nxt;
    while(!Q.empty())
    {
        u=Q.front(); Q.pop(); flag[u]=0;
        for(unsigned int i=0;i<Map[u].size();i++)
        {
            v=Map[u][i],nxt=dist[u]+Val[u][i];
            if(nxt>=dist[v]) continue;
			dist[v]=nxt; if(flag[v]) continue;
			Q.push(v); flag[v]=1;
        }
    }
}

inline void AddEdge(int u,int v,int t,int c,int n)
{
	Map[u].push_back(v); Val[u].push_back(t); Cost[u].push_back(c);  Num[u].push_back(n);
}

void init()
{
	scanf("%d %d\n",&N,&M);
	for(int u,v,t,c,i=1;i<=M;i++)
	{
		scanf("%d %d %d %d\n",&u,&v,&t,&c);
		AddEdge(u,v,t,c,i);   AddEdge(v,u,t,c,i);
	}
}

int Ans=0,P=1;
class NODE
{
public:
    int node,c,next,num;
}Node[MAXN];
int start[MAXN];
 int level[MAXN],now[MAXN];
void AddEdgee(int a,int b,int c,int n)
{
    P++;Node[P].node=b,Node[P].next=start[a],start[a]=P,Node[P].c=c,Node[P].num=n;
    P++;Node[P].node=a,Node[P].next=start[b],start[b]=P,Node[P].c=0,Node[P].num=n;
}

bool BFS()
{
    memset(level,0,sizeof(level));
    memcpy(now,start,T+1<<2);
    level[T]=1; 
    while(!Q.empty()) Q.pop();
    Q.push(T);
    int u;
    while(!Q.empty())
    {
        u=Q.front(); Q.pop();
        for(int i=start[u],v=Node[i].node;i;i=Node[i].next,v=Node[i].node)
        {
            if(Node[i^1].c && !level[v] )
            {
                Q.push(v);
                level[v]=level[u]+1;
                if(v==S) return 1;
            }
        }
    }
    return 0;
}

inline int Min(int a,int b) {return a<b?a:b;}
 
int Dinic(int u,int l)
{
    if(u==T) return l;
    int t=l,tmp;
    for (int i=now[u],v=Node[i].node;i;now[u]=i=Node[i].next,v=Node[i].node)
    {
        if(Node[i].c&&level[v]==level[u]-1)
        {
            tmp=Dinic(v,Min(l,Node[i].c));
            Node[i].c-=tmp;Node[i^1].c+=tmp;
            l-=tmp;
            if (l==0) break;                              
        }
    }
    if (l==t) level[u]=-1;
    return t-l; 
} 

void solve()
{
	SPFA(1,N,dist1);  SPFA(N,1,dist2);
	//for(int i=1;i<=N;i++) printf("%d--->%d   %d\n",i,dist1[i],dist2[i]);
	printf("%d\n",dist1[N]); 
	int v,t,n;
	for(int i=1;i<=N;i++)
	{
		for(unsigned int k=0;k<Map[i].size();k++)
		{
			v=Map[i][k],t=Val[i][k],n=Num[i][k];
			if(dist1[i]+t+dist2[v]!=dist1[N]) continue;
			AddEdgee(i,v,Cost[i][k],n);
		}
	}  S=1,T=N;
	while(BFS()) Ans+=Dinic(S,INF);
	//printf("%d\n",Ans);
	BFS();  VEC Cut;
	for(int k=1;k<=N;k++)
	{
		for(int i=start[k],v=Node[i].node;i;i=Node[i].next,v=Node[i].node)
		{
			if(level[k]<=0 || level[v]<=0) continue;
			Cut.push_back(Node[i].num);
		}
	}
	printf("%d %d\n",Cut.size(),Ans);
	for(unsigned int i=0;i<Cut.size();i++) printf("%d\n",Cut[i]);
}

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