낙 곡 - P3381 [템 플 릿] 최소 비용 최대 흐름 (최소 비용 루트 알고리즘)

제목 설명
예 를 들 어 하나의 네트워크 그림 과 그 원점 과 외환 점 을 제시 하고 모든 변 에서 그의 최대 유량 과 단위 유량 비용 을 알 고 네트워크 의 최대 흐름 과 최대 흐름 상황 에서 의 최소 비용 을 구한다.
입력 형식:
첫 번 째 줄 은 네 개의 정수 N, M, S, T 를 포함 하고 각각 점 의 개수, 방향 변 의 개수, 원점 번호, 어 셈 블 리 번 호 를 나타 낸다.
그 다음 에 M 줄 은 각 줄 에 네 개의 정수 ui, vi, wi, fi 를 포함 하고 제 i 조 는 ui 에서 출발 하여 vi 에 도착 하고 변 권 은 wi (즉 이 변 의 최대 유량 은 wi) 이 며 단위 유량 의 비용 은 fi 임 을 나타 낸다.
출력 형식:
한 줄 은 두 개의 정 수 를 포함 하고 최대 유량 과 최대 유량 상황 에서 의 최소 비용 이다.
샘플 입력 \ # 1:

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

출력 샘플 \ # 1:

50 280

사고의 방향
제목 의 뜻 은 매우 간단 하 다. 바로 최소 비용 흐름 을 구 하 는 것 이다. 주로 알고리즘 을 말 해 보 자.
최소 비용 로 알고리즘 은 최소 비용 로 를 찾 아 이 경로 에서 증 류 를 하고 최대 흐름 으로 늘 리 는 것 이 사상 이다.
인접 표를 이용 하여 양 방향 변 을 만 들 고 정방 향 변 의 비용 은 cost 이 며, 반대 변 의 비용 은 -cost 입 니 다. 최소 비용 로 를 찾 을 때 원점 에서 출발 하여 실행 가능 (E [i]. cap > E [i]. flow) 을 따라 각 인접 점 을 광범 위 하 게 검색 합 니 다. 현재 변 이 계속 느슨 해 지면 업데이트 하 는 것 이 SPFA 알고리즘 입 니 다.
최소 비용 길 을 찾 은 후에 외환 점 에서 원점 으로 하 나 를 찾 고 최소 의 유량 을 증가 할 수 있 으 며 넓 은 길 을 따라 흐름 을 증가 하고 역방향 으로 줄 이 며 마지막 으로 사용 하 는 비용 은 다음 과 같다.
mincost=dis[V]∗d
이 과정 을 누적 하여 구 한 것 은 최소 비용 이 고, 최대 흐름 은 매번 누적 할 수 있 는 유량 이다.
코드

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=5000+20;
const int M=50000+20;

int top;//     
int dis[N],pre[N];//    i     ，pre[i]    
bool vis[N];//    
int maxflow;
int first[N];//     
struct Edge
{
    int v,next;
    int cap,flow,cost;
} E[M*2];

void init()
{
    mem(first,-1);
    top=0;
    maxflow=0;
}

void add_edge(int u,int v,int c,int cost)
{
    E[top].v=v;
    E[top].cap=c;
    E[top].flow=0;
    E[top].cost=cost;
    E[top].next=first[u];
    first[u]=top++;
}
void add(int u,int v,int c,int cost)
{
    add_edge(u,v,c,cost);
    add_edge(v,u,0,-cost);
}
bool spfa(int s,int t,int n)
{
    int i,u,v;
    queue<int>q;
    mem(vis,false);
    mem(pre,-1);
    for(int i=1; i<=n; i++) dis[i]=inf;
    vis[s]=true;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=first[u]; i!=-1; i=E[i].next)
        {
            v=E[i].v;
            if(E[i].cap>E[i].flow&&dis[v]>dis[u]+E[i].cost)
            {
                dis[v]=dis[u]+E[i].cost;
                pre[v]=i;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    if(dis[t]==inf)
        return false;
    return true;
}
int MCMF(int s,int t,int n)//minCostMaxFlow
{
    int d;
    int i,mincost=0;//maxflow      ，mincost      
    while(spfa(s,t,n))//      s t      
    {
        d=inf;
        for(int i=pre[t]; i!=-1; i=pre[E[i^1].v]) //     
            d=min(d,E[i].cap-E[i].flow);
        maxflow+=d;//     
        for(int i=pre[t]; i!=-1; i=pre[E[i^1].v]) //         +d,     -d
        {
            E[i].flow+=d;
            E[i^1].flow-=d;
        }
        mincost+=dis[t]*d;//dis[t]             
    }
    return mincost;
}
int main()
{
    int n,m,st,ed;
    int u,v,w,c;
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    init();
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d%d",&u,&v,&w,&c);
        add(u,v,w,c);
    }
    int mincost=MCMF(st,ed,n);
    printf("%d %d
",maxflow,mincost);
    return 0;
}