rt

附上最新一版卡常代码

#pragma optimize(1)
#pragma optimize(2)
#pragma optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N=409;
const int M=15009;
const int inf=1e9;
int n,m,s,t;
int dis[N],flow[N],rad[N];
int ans1,ans2;
bool vis[N];
struct edge{
	int to,c,d;
	int nxt;
}e[M*2];
int hed[N],ecnt;
inline void add(int l,int r,int c,int d){
	e[ecnt].to=r;
	e[ecnt].c=c;
	e[ecnt].d=d;
	e[ecnt].nxt=hed[l];
	hed[l]=ecnt;
	ecnt++;
}
deque<int> q;
inline bool spfa(){
	for(register int i=1;i<=n;i++) dis[i]=inf;
	memset(vis,0,sizeof vis);
	q.push_back(s);
	vis[s]=1;
	dis[s]=0;
	long long sum=0,len=1;
	while(!q.empty()){
		if(q.size()>1&&(dis[q.front()]>dis[q.back()])){
			swap(q.front(),q.back());
		}
		int cur=q.front();
		q.pop_front();
		if(dis[cur]*len>sum){//lll
			q.push_back(cur);
			continue;
		}
		vis[cur]=0;
		sum-=dis[cur];
		len--;
		for(register int i=hed[cur];i!=-1;i=e[i].nxt){
			if(e[i].c&&dis[e[i].to]>dis[cur]+e[i].d){
				dis[e[i].to]=dis[cur]+e[i].d;
				flow[e[i].to]=min(flow[cur],e[i].c);
				if(!vis[e[i].to]){
					if(!q.empty()&&dis[e[i].to]<dis[q.front()]) q.push_front(e[i].to);
                	else q.push_back(e[i].to);
					vis[e[i].to]=1;
					sum+=dis[e[i].to];
					len++;					
				}
			}
		}
	}
	return dis[t]<inf;
}
inline int dfs(int start,int flow){
	int cnt=0;
	vis[start]=1;
	if(start==t) return flow;
	for(register int i=rad[start];i!=-1&&flow;i=e[i].nxt){
		rad[start]=i;
		if(!vis[e[i].to]&&dis[e[i].to]==dis[start]+e[i].d&&e[i].c){
			int ret=dfs(e[i].to,min(flow,e[i].c));
			e[i].c-=ret;
			e[i^1].c+=ret;
			cnt+=ret;
			flow-=ret;
			ans2+=ret*e[i].d;
			if(!flow) break;
		}
	}
	vis[start]=0;
	if(!cnt) dis[start]=-1;
	return cnt;
}
struct FastIO{
    static const int S=1048576;char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
    inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('\n');}
    FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='\n');return *this;}
    template<typename T>FastIO& operator >> (T&ret)
    {
        ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
    }
    FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
    template<typename T>FastIO& operator << (T x)
    {
        if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
        while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
    }
    FastIO& operator << (char ch){pc(ch);return *this;}
    FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
	memset(hed,-1,sizeof hed);
	cin>>n>>m;
	s=1,t=n;
	for(register int i=0;i<m;i++){
		int u,v,w,c;
//		u=read(),v=read(),w=read(),c=read();
		fin>>u>>v>>w>>c;
		add(u,v,w,c);
		add(v,u,0,-c);
	}
	while(spfa()) memcpy(rad,hed,(n+1)*sizeof(int)),ans1+=dfs(s,inf);
	cout<<ans1<<" "<<ans2<<endl;
	return 0;
}