每日归档： 2019年1月15日

首先我们需要掌握网络流的相关知识。
然后，我们仔细观察费用流问题，我们发现，这一类问题的本质上就是让我们求一个带路径长度的最大流。
故而，我们考虑，对于相同的流量，尽可能地从费用小的一条路走过去——这是一种很显然的贪心。
具体的实现似乎也并不难，只需要将原来的朴素求法（EK）稍微更改一下，将反边的花费变成相反数，然后求最短路即可。
考虑到负权边的可能，用SPFA会比较快。当然如果只有正权边显然是可以Dijkstra的。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
    return A<B?A:B;
}
struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[100005];
int h[5005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);Eadd(V,U,0,-C);
}
int n,m,s,t,dis[5005],val[5005],fa[5005],nw[5005];
bool vis[5005];
std::queue<int> q;
inline int spfa(){
	for(int i=1;i<=n;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	while(!q.empty()){
		q.pop();
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}
void init(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int u,v,w,c;
    for(int i=1;i<=n;++i){
        h[i]=-1;
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&u,&v,&w,&c);
        add(u,v,w,c);
    }
    int ansW=0,ansC=0,p;
    while(spfa()){
    	p=t;
    	ansW+=val[t];
    	ansC+=val[t]*dis[t];
    	while(p!=s){
    		e[nw[p]].w-=val[t];
    		e[nw[p]^1].w+=val[t];
    		p=fa[p];
		} 
    }
    printf("%d %d\n",ansW,ansC);
}

int main(){
    init();
    return 0; 
}