记录

代码：

#include<bits/stdc++.h>
using namespace std;
#pragma optimize(1)
#pragma optimize(2)
#pragma optimize(3,"Ofast","inline")
const int N=409;
const int M=15009;
const int inf=1e9;
int n,m,s,t;
int dis[N],flow[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;
   for(register int i=1;i<=n;i++) vis[i]=0;
   q.push_back(s);
   vis[s]=1;
   dis[s]=0;
   while(!q.empty()){
   	int cur=q.front();
   	q.pop_front();
   	vis[cur]=0;
   	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;
   			}
   		}
   	}
   }
   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=hed[start];i!=-1&&flow;i=e[i].nxt){ 
   	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;
   	}
   }
   vis[start]=0;
   return cnt; 
}
inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
   return x*f;
}
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();
   	add(u,v,w,c);
   	add(v,u,0,-c);
   }
   while(spfa()) ans1+=dfs(s,inf);
   cout<<ans1<<" "<<ans2<<endl;
   return 0;
}