@[紫钦](/space/show?uid=37839)
附评测记录：
两个AC分别是O2和极力卡常的结果。
[评测记录](https://www.luogu.org/recordnew/lists?uid=37839&pid=P3381)。
by 紫钦 @ 2018-06-20 00:12:54
正常写就过了啊。。
用了vector和queue
by 文文殿下 @ 2018-06-20 07:18:19
EK明明很快的==
by かなで @ 2018-06-20 08:16:15
这题不是prime Dual随便跑么，而且跑的还贼快
by Victorique @ 2018-06-20 08:34:47
我觉得我写的很正常啊。。。
by 紫钦 @ 2018-06-20 12:31:39
```cpp
//-O2可以AC
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
namespace Qza {
const int N=5005;
const int M=50005;
int n,m,S,T,maxflow,mincost;
int en[N],nex[M<<1],to[M<<1],w[M<<1],c[M<<1];
int flow[N],cost[N],pre[N],las[N]; // 每个点的本次增广最大流量、最小费用、前驱点，前驱边。
bool vis[N];
char buf[10000000],*buf_S,*buf_T;
queue <int> Q;
bool spfa(int &s,int &t)
{
memset(flow,0x3f,sizeof(flow));
memset(cost,0x3f,sizeof(cost));
memset(vis,false,sizeof(vis ));
while(!Q.empty()) vis[Q.front()]=false, Q.pop();
Q.push(s); // 写成push()会炸，因为此时队列没有头。。。
vis[s]=true;
cost[s]=0;
pre[t]=0;
register int x;
while(!Q.empty()) {
x=Q.front();
Q.pop();
vis[x]=false;
for(int p=en[x];~p;p=nex[p]) {
if(w[p] && cost[to[p]]>cost[x]+c[p]) {
cost[to[p]]=cost[x]+c[p];
pre[to[p]]=x;
las[to[p]]=p;
flow[to[p]]=min(flow[x],w[p]);
if(!vis[to[p]]) {
if(cost[to[p]]>cost[Q.front()])
Q.push(to[p]);
else
Q.push(to[p]);
vis[to[p]]=true;
}
}
}
}
return pre[t];
}
void Maxflow_Mincost_Dinic(int &s,int &t)
{
int x=0;
while(spfa(s,t)) {
register int cur=t;
maxflow+=flow[t];
mincost+=flow[t]*cost[t];
while(cur!=s) {
w[las[cur]]-=flow[t];
w[las[cur]^1]+=flow[t];
cur=pre[cur];
}
}
}
char get_char()
{
if(buf_S==buf_T) {
buf_T=(buf_S=buf)+fread(buf,1,10000000,stdin)-1;
if(buf_S==buf_T) return EOF;
return *buf_S;
}
return *++buf_S;
}
#define getchar get_char
int read()
{
char ch=getchar(); int x=0;
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
return x;
}
void main()
{
int cnt=-1;
int u,v;
memset(en,-1,sizeof(en));
n=read(); m=read(); S=read(); T=read();
for(int i=1;i<=m;++i) { // 这个地方是m，而不是n。
u=read(); v=read();
nex[++cnt]=en[u]; to[cnt]=v; en[u]=cnt; w[cnt]=read(); c[cnt]=read();// printf("%d %d\n",w[cnt],c[cnt]);
nex[++cnt]=en[v]; to[cnt]=u; en[v]=cnt; w[cnt]=0;c[cnt]=-c[cnt-1];
}
Maxflow_Mincost_Dinic(S,T);
printf("%d %d",maxflow,mincost);
}
}
int main()
{
Qza::main();
return 0;
}
```
by 紫钦 @ 2018-06-20 12:38:11
@[文文殿下](/space/show?uid=64618)
by 紫钦 @ 2018-06-20 12:38:45
@[Victorique](/space/show?uid=49223)
可能我比较菜。。。
by 紫钦 @ 2018-06-20 12:39:04
```cpp
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
namespace MCMF{
const int maxn=6000,INF=100000;
struct Edge {
int from,to,cap,cost,flow;
Edge(int from,int to,int cap,int cost):from(from),to(to),cap(cap),cost(cost) {
flow=0;
}
};
int n,m,s,t;
std::vector<Edge> edges;
std::vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn];
void init(int n) {
MCMF::n=n;
for(register int i=0;i<n;++i) G[i].clear();
edges.clear();
}
void addEdge(int from,int to,int cap,int cost) {
edges.push_back(Edge(from,to,cap,cost));
edges.push_back(Edge(to,from,0,-cost));
int m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BellmanFord(int s,int t,int &flow,int &cost) {
for(register int i=1;i<=n;i++) {
d[i]=INF;
}
memset(inq,0,sizeof(inq));
d[s]=0;
inq[s]=1;
p[s]=0;
a[s]=INF;
std::queue<int> Q;
Q.push(s);
while(!Q.empty()) {
int u=Q.front();Q.pop();
inq[u]=0;
for(register int i=0;i<G[u].size();++i) {
Edge& e =edges[G[u][i]];
if(e.cap>e.flow&&d[e.to]>d[u]+e.cost) {
d[e.to]=d[u]+e.cost;
p[e.to]=G[u][i];
a[e.to]=std::min(a[u],e.cap-e.flow);
if(!inq[e.to]) {
Q.push(e.to);
inq[e.to]=1;
}
}
}
}
if(d[t]==INF) return false;
flow+=a[t];
cost+=a[t]*d[t];
int u=t;
while(u!=s) {
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
u=edges[p[u]].from;
}
return true;
}
void minCost(int s,int t,int& flow,int& cost) {
flow=0;
cost=0;
while(BellmanFord(s,t,flow,cost));
return;
}
}
int n,m,s,t,a,b,c,cs;
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
MCMF::init(n);
while(m--) {
scanf("%d%d%d%d",&a,&b,&c,&cs);
MCMF::addEdge(a,b,c,cs);
}
int flow,cost;
MCMF::minCost(s,t,flow,cost);
printf("%d %d",flow,cost);
return 0;
}
```
by 文文殿下 @ 2018-06-20 14:58:12
@[文文殿下](/space/show?uid=64618)
你的代码在我的机子上跑了1.5s。。。
by 紫钦 @ 2018-06-21 22:58:44