bzoj 1834 [ZJOI 2010] 네트워크 확장 [최대 흐름 + 비용 흐름]

첫 번 째 질문 은 간단 하 다.
두 번 째 질문 비용 흐름 은 주로 그림 을 만 드 는 것 이다. 그러면 첫 번 째 질문 의 잔류 네트워크 에서 그림 을 계속 만 들 수 있다. 잔류 네트워크 의 모든 변 에 하나의 용량 을 만 드 는 것 은 표시 비용 은 w 의 변 (역방향 아크 용량 은 0 이 고 비용 은 - w) 이다. 그 다음 에 슈퍼 소스 를 만 들 고 슈퍼 소스 에서 1 개의 용량 은 k 이 며 비용 은 0 의 변 (통제 용) 이다.이 그림 에 대해 최소 비용 의 최대 흐름 알고리즘 을 진행 하 다.
       최소 비용 최대 흐름 조작:
       1. 우선 이 문제 의 그림 에 있어 서 어떤 것 은 비용 을 써 야 하고 어떤 것 은 사용 하지 않 아 도 되 며 확대 하지 않 아 도 되 는 변 비용 은 0 이 고 확대 해 야 하 는 변 비용 은 w 이 며 용량 은 무한 하 다. 이것 이 바로 본 문제 가 이렇게 그림 을 만 드 는 원인 이다.
       2. 잔류 네트워크 진행 비용 최 단 로 SPFA 알고리즘, 확장 하지 않 는 변 은 반드시 비용 이 0 인 변 을 선택 한 다음 에 경 로 를 기록 하고 최소 용량 을 찾 아 실행 가능 한 길 을 증가 시 켜 ans 를 업데이트 합 니 다.

/**************************************************************
    Problem: 1834
    User: BPM136
    Language: C++
    Result: Accepted
    Time:52 ms
    Memory:2520 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#define LL long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define efo(i,x) for(int i=last[x];i!=0;i=e[i].next)
using namespace std;
inline LL read()
{
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}
#define N 1005
#define M 5005
#define inf 100000007
struct edge
{
    int x,y,next,w,c,f;
}e[M*10];
int last[N*5],ne=1;
int n,m,mn,ans=0;
 
void add11(int x,int y,int f,int w)
{
    e[++ne].x=x;e[ne].y=y;e[ne].f=f;e[ne].w=w;e[ne].next=last[x];last[x]=ne;
}
void add12(int x,int y,int f,int w)
{
    add11(x,y,f,w);add11(y,x,0,-w);
}
 
void init()
{
    n=read(),m=read();mn=read();
    fo(i,1,m)
    {
        int x=read(),y=read(),w=read(),c=read();
        add12(x,y,w,c);
    }
}
 
int q[N*9],high[N];
bitset<N>inq;
bool bfs(int s,int tt)
{
    inq.reset();
    memset(high,0,sizeof(high));
    int h=0,t=1;
    q[1]=s;inq[s]=1;high[s]=1;
    while(h<t)
    {
        int now=q[++h];
        if(now==tt)return 1;
        efo(i,now)
        if(e[i].f&&high[e[i].y]==0)
        {
            high[e[i].y]=high[now]+1;
            q[++t]=e[i].y;
        }
//      inq[now]=0;
    }
    return 0;
}
 
int dfs(int s,int maxf,int t)
{
    if(s==t)return maxf;
    int ret=0,f;
    efo(i,s)
    if(e[i].f&&high[e[i].y]==high[s]+1)
    {
        f=dfs(e[i].y,min(maxf-ret,e[i].f),t);
        e[i].f-=f;
        e[i^1].f+=f;
        ret+=f;
        if(ret==maxf)return ret;
    }
    return ret;
}
 
int dinic(int s,int t)
{
    int ret=0;
    while(bfs(s,t))ret+=dfs(s,inf,t);
    return ret;
}
 
void add21(int x,int y,int f,int c)
{
    e[++ne].x=x;e[ne].y=y;e[ne].f=f;e[ne].c=c;e[ne].next=last[x];last[x]=ne;
}
void add22(int x,int y,int f,int c)
{
    add21(x,y,f,c);add21(y,x,0,-c);
}
 
void build()
{
    int t=ne;
    fo(i,2,t)
    if(i%2==0)
    add22(e[i].x,e[i].y,inf,e[i].w);
     
    add21(n+1,1,mn,0);
}
 
int dis[N],pre[N],lo[N];
bool spfa(int s,int tt)
{
    inq.reset();
    fo(i,0,N-1)dis[i]=inf;
    memset(pre,0,sizeof(pre));
    memset(lo,0,sizeof(lo));
    int h=0,t=1;
    q[1]=s;dis[s]=0;inq[s]=1;
    while(h<t)
    {
        int now=q[++h];
        efo(i,now)
        if(e[i].f&&dis[now]+e[i].c<dis[e[i].y])
        {
            dis[e[i].y]=dis[now]+e[i].c;
            pre[e[i].y]=now;
            lo[e[i].y]=i;
            if(inq[e[i].y]==0)
            {
                inq[e[i].y]=1;
                q[++t]=e[i].y;
            }
        }
        inq[now]=0;
    }
    if(dis[tt]==inf)return 0;
    else return 1;
}
 
void mcf(int s,int t)
{
    while(spfa(s,t))
    {
        int x=t,mi=inf;
        while(pre[x]!=0)
        {
            mi=min(mi,e[lo[x]].f);
            x=pre[x];
        }
        x=t;
        while(pre[x]!=0)
        {
            ans+=mi*e[lo[x]].c;
            e[lo[x]].f-=mi;
            e[lo[x]^1].f+=mi;
            x=pre[x];
        }
    }
}   
 
int main()
{
    init();
    ans=dinic(1,n);
    printf("%d ",ans);
    ans=0;
    build();
    mcf(n+1,n);
    printf("%d",ans);
    return 0;
}