费用流板子
细节真多……一个边的flow和点的flow分不清……还有往回减流的时候应该减去flow[t]……
1 //minamoto 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf;10 inline int read(){11 #define num ch-'0'12 char ch;bool flag=0;int res;13 while(!isdigit(ch=getc()))14 (ch=='-')&&(flag=true);15 for(res=num;isdigit(ch=getc());res=res*10+num);16 (flag)&&(res=-res);17 #undef num18 return res;19 }20 const int N=5005,M=100005;21 bool vis[N];22 int n,m,s,t,u,v,e,f,dis[N],Pre[N],last[N],disf[N],maxflow,mincost;23 int head[N],Next[M],ver[M],edge[M],flow[M],tot=1;24 queue q;25 inline void add(int u,int v,int f,int e){26 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e,flow[tot]=f;27 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=-e,flow[tot]=0;28 }29 bool spfa(){30 memset(dis,0x3f,sizeof(dis));31 memset(disf,0x3f,sizeof(disf));32 memset(vis,0,sizeof(vis));33 q.push(s),vis[s]=1,dis[s]=0,Pre[t]=-1;34 while(!q.empty()){35 int u=q.front();q.pop();vis[u]=0;36 for(int i=head[u];i;i=Next[i]){37 int v=ver[i];38 if(flow[i]>0&&dis[v]>dis[u]+edge[i]){39 dis[v]=dis[u]+edge[i];40 Pre[v]=u;41 last[v]=i;42 disf[v]=min(disf[u],flow[i]);43 if(!vis[v]){44 vis[v]=1,q.push(v);45 }46 }47 }48 }49 return Pre[t]!=-1;50 }51 void MCMF(){52 while(spfa()){53 int u=t;54 maxflow+=disf[t];55 mincost+=disf[t]*dis[t];56 while(u!=s){57 flow[last[u]]-=disf[t];58 flow[last[u]^1]+=disf[t];59 u=Pre[u];60 }61 }62 }63 int main(){64 n=read(),m=read(),s=read(),t=read();65 for(int i=1;i<=m;++i){66 u=read(),v=read(),f=read(),e=read();67 add(u,v,f,e);68 }69 MCMF();70 printf("%d %d\n",maxflow,mincost);71 return 0;72 }