네트워크 플로우(일반적 구현, 구조체로 구현)

const int MAX_N=100,MAX_V=MAX_N*2+2,INF=987654321;
int N,M,S=MAX_V-2,E=MAX_V-1,capacity[MAX_V][MAX_V],flow[MAX_V][MAX_V];
vector<int> adj[MAX_V];

int networkFlow(int source,int sink)
{
    memset(flow,0,sizeof(flow));
    int totalSum=0;
    while(true)
    {
        vector <int> parent(MAX_V,-1);
        queue <int> q;
        parent[source]=source;
        q.push(source);
        while(!q.empty()&&parent[sink]==-1)
        {
            int now=q.front();q.pop();
            for(auto next:adj[now])
            {
                if(capacity[now][next]-flow[now][next]>0 && parent[next]==-1)
                {
                    q.push(next);
                    parent[next]=now;
                }
            }
        }
        if(parent[sink]==-1) break;
        int sum=INF;
        for(int p=sink;p!=source;p=parent[p])
            sum=min(capacity[parent[p]][p]-flow[parent[p]][p],sum);
        for(int p=sink;p!=source;p=parent[p])
        {
            flow[parent[p]][p]+=sum;
            flow[p][parent[p]]-=sum;
        }
        totalSum+=sum;
    }
    return totalSum;
}

가장 일반적인 형태의 그래프일때 최대로 흘려보낼수있는 유량을 구하는 함수입니다.

---

 

const int MAX_N=400,MAX_V=MAX_N*2+2,INF=987654321;
int S=MAX_V-2,E=MAX_V-1,N,M,capacity[MAX_V][MAX_V],flow[MAX_V][MAX_V],cost[MAX_V][MAX_V];
vector<int>adj[MAX_V];

int networkFlow(int source,int sink)
{
    memset(flow,0,sizeof(flow));
    int totalSum=0;
    while(true)
    {
        vector<int>parent(MAX_V,-1),dist(MAX_V,INF);
        bool inQ[MAX_V]={0,};
        queue<int>q;

        parent[source]=source;
        dist[source]=0;
        inQ[source]=true;
        q.push(source);

        while(!q.empty())
        {
            int now=q.front();q.pop();
            inQ[now]=false;
            for(auto next:adj[now])
            {
                if(capacity[now][next]-flow[now][next]>0 &&
                   dist[next]>dist[now]+cost[now][next])
                {
                    dist[next]=dist[now]+cost[now][next];
                    parent[next]=now;
                    if(!inQ[next])
                    {
                        inQ[next]=true;
                        q.push(next);
                    }
                }
            }
        }
        if(parent[sink]==-1) break;
        int sum=INF;
        for(int p=sink;p!=source;p=parent[p])
            sum=min(capacity[parent[p]][p]-flow[parent[p]][p],sum);
        for(int p=sink;p!=source;p=parent[p])
        {
            totalSum+=sum*cost[parent[p]][p];
            flow[parent[p]][p]+=sum;
            flow[p][parent[p]]-=sum;
        }
    }
    return totalSum;
}

 

각 간선마다 cost만큼의 비용이들때, 최소의 비용을갖는 최대의 유량을 찾는 최소 비용 최대 유량(Minimum Cost Maximum Flow)문제의 함수입니다.

 

---

 

위와같이 노드와 노드와의 관계를 2차원의 배열로관리하면 MAX_V*2만큼의 공간복잡도가 발생합니다. 따라서 모든 문제를 이와같이 풀수있는건 아닙니다.  MAX_V가1만이라도 넘어버리면 대게 메모리초과를 뱉어냅니다. 이를위해서 간선을 구조체로 관리하여서 공간복잡도를 줄일 수 있습니다. 

const int MAX_N=1000,MAX_V=MAX_N+2,INF=(int)1e9+7;
int S=MAX_V-2,E=MAX_V-1,N,M;

struct EDGE
{
    int to,capacity,flow;
    EDGE* rev;
    EDGE(int to,int capacity):to(to),capacity(capacity),flow(0){}
    int getCap(){return capacity-flow;}
    void addFlow(int f)
    {
        flow+=f;
        rev->flow-=f;
    }
};
vector<EDGE*>adj[MAX_V];

int networkFlow(int source,int sink)
{
    int totalFlow = 0;
	while(true)
    {
        vector<int>prev(MAX_V,-1);
		EDGE *edge[MAX_V];
		queue<int> q;
		prev[source]=source;
		q.push(source);

		while(!q.empty() && prev[sink] == -1)
        {
			int now = q.front();
			q.pop();
			for(EDGE *e: adj[now]){
				int next = e->to;
				if(e->getCap() > 0 && prev[next] == -1){
					prev[next] = now;
					edge[next] = e;
					q.push(next);
				}
			}
		}
		if(prev[sink] == -1) break;

		int flow = INF;
		for(int i=sink; i!=source; i=prev[i])
			flow = min(flow, edge[i]->getCap());
		for(int i=sink; i!=source; i=prev[i])
			edge[i]->addFlow(flow);
		totalFlow += flow;
	}
	return totalFlow;
}

void connect(int u,int v,int cap)
{
    EDGE*uv=new EDGE(v,cap),*vu=new EDGE(u,0);
    uv->rev=vu,vu->rev=uv;
    adj[u].push_back(uv);
    adj[v].push_back(vu);
}

 

---

마찬가지로 MCMF 유형의 문제를 풀때의 구조체 코드입니다.

 

const int MAX_N=1000,MAX_V=MAX_N*2+2,INF=987654321;
int N,M;

struct Edge
{
    int to, capacity, flow, cost;
    Edge *rev;
    Edge(int to=-1, int capacity=0, int cost=0) : to(to),capacity(capacity),cost(cost),flow(0){}
    void addFlow(int f)
    {
        flow+=f;
        rev->flow-=f;
    }
    int getCap() {return capacity-flow;}
};
vector<Edge*> adj[MAX_V];

void connect(int u,int v,int cap,int cost)
{
    Edge *uv = new Edge(v,cap,cost),*vu = new Edge(u,0,-cost);
    uv->rev = vu;
    vu->rev = uv;
    adj[u].push_back(uv);
    adj[v].push_back(vu);
}

int networkFlow(int source,int sink)
{
    int totalFlow=0,totalCost=0;
    while (true)
    {
        queue<int> q;
        vector<int>prev(MAX_V,-1),dist(MAX_V,INF);
        bool inQ[MAX_V]={0,};
        Edge *edge[MAX_V];

        dist[source] = 0;
        inQ[source] = true;
        q.push(source);

        while (!q.empty())
        {
            int now = q.front();
            q.pop();
            inQ[now] = false;

            for (Edge *e : adj[now])
            {
                int next = e->to;
                if (e->getCap() > 0 && dist[next] > dist[now] + e->cost)
                {
                    prev[next] = now;
                    edge[next] = e;
                    dist[next] = dist[now] + e->cost;
                    if (!inQ[next])
                    {
                        q.push(next);
                        inQ[next] = true;
                    }
                }
            }
        }

        if (prev[sink] == -1) break;

        int flow = INF;
        for (int i = sink; i != source; i = prev[i])
            flow = min(flow, edge[i]->getCap());
        for (int i = sink; i != source; i = prev[i])
        {
            edge[i]->addFlow(flow);
            totalCost += flow*edge[i]->cost;
        }

        totalFlow += flow;
    }
    return totalCost;
}

문제에따라 totalFlow를 같이물어보는 경우가있으니, 리턴값을 int형이든 pair<int,int>형이든 변환하여 사용하면 됩니다. 배열로 구현할때와달리 메모리가 획기적으로 줄어듭니다.