rt，

SPFA 998ms 成功复活！

评测记录

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
const int maxn=405,maxe=15005;
namespace in{
    #ifdef faster
    char buf[1<<21],*p1=buf,*p2=buf;
    inline int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    #else
    inline int getc(){return getchar();}
    #endif
    template <typename T>inline void read(T& t){
        t=0;int f=0;char ch=getc();while (!isdigit(ch)){if(ch=='-')f = 1;ch=getc();}
        while(isdigit(ch)){t=t*10+ch-48;ch = getc();}if(f)t=-t;
    }
    template <typename T,typename... Args> inline void read(T& t, Args&... args){read(t);read(args...);}
}
namespace out{
    char buffer[1<<21];int p1=-1;const int p2 = (1<<21)-1;
    inline void flush(){fwrite(buffer,1,p1+1,stdout),p1=-1;}
    inline void putc(const char &x) {if(p1==p2)flush();buffer[++p1]=x;}
    template <typename T>void write(T x) {
        static char buf[15];static int len=-1;if(x>=0){do{buf[++len]=x%10+48,x/=10;}while (x);}else{putc('-');do {buf[++len]=-(x%10)+48,x/=10;}while(x);}
        while (len>=0)putc(buf[len]),--len;
    }
}
struct Edge{
	int v,w,c,nxt;
	Edge() {}
	Edge(int _v,int _w,int _c,int _nxt) {
		v=_v; w=_w; c=_c; nxt=_nxt;
	}
}edge[maxe<<1];
int n,m,s,t,head[maxn],ecnt,maxflow=0,mincost=0;
inline void init()
{
	ecnt=0;
	memset(head,-1,sizeof(head));
}
inline void addedge(int u,int v,int w,int c)
{
	edge[ecnt]=Edge(v,w,c,head[u]);
	head[u]=ecnt++;
}
int flow[maxn],pre[maxn],dis[maxn];
queue<int> que;
bool inq[maxn];
int opo[maxn<<4],opopo;
inline bool spfa(int s,int t)
{
	For(i,1,opopo)
		dis[opo[i]]=pre[opo[i]]=-1,flow[opo[i]]=0x3f3f3f3f;
	opopo=0;
	dis[s]=0;
	que.push(s);
	inq[s]=true;
	while(!que.empty())
	{
		register int u=que.front();
		que.pop();
		inq[u]=false;
		for(register int i=head[u];i!=-1;i=edge[i].nxt)
		{
			register int v=edge[i].v,c=edge[i].c;
			if(edge[i].w&&(dis[v]==-1||dis[v]>dis[u]+c))
			{
				opo[++opopo]=v;
				dis[v]=dis[u]+c;
				pre[v]=i;
				flow[v]=min(edge[i].w,flow[u]);
				if(!inq[v])
				{
					que.push(v);
					inq[v]=true;
				}
			}
		}
	}
	return pre[t]!=-1;
}
int main()
{
	in::read(n,m);
	s=1,t=n;
	init();
	register int u,v,w,c;
	while(m--)
	{
		in::read(u,v,w,c);
		addedge(u,v,w,c);
		addedge(v,u,0,-c);
	}
	memset(dis,-1,sizeof(dis));
	memset(pre,-1,sizeof(pre));
	memset(flow,0x3f,sizeof(flow));
	while(spfa(s,t))
	{
		maxflow+=flow[t];
		mincost+=flow[t]*dis[t];
		for(register int u=t;u^s;u=edge[pre[u]^1].v)
		{
			edge[pre[u]].w-=flow[t];
			edge[pre[u]^1].w+=flow[t];
		}
	}
	cout<<maxflow<<' '<<mincost<<endl;
	return 0;
}