글 읽기 - mcmf 모델링 칙칙폭폭

lyzqm 6년 전 0

이 문제 힌트보고 풀긴 풀었는데 기차에서 내리는작업을 i번째와 i+1번째 정점을 capacity가 INF, cost 0으로 연결해주는 작업으로

해주는데 직관적으로 이해하기가 어렵네요 ㅠㅠ

설명해주실분 있나요?

smu201111192 6년 전 0

코드를 보여주실 수 있나용?

lyzqm 6년 전 0

여기있습니다 !

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 987654321

struct MCMF{
   struct Edge{
      int v, rev, cap, cost;
      Edge(){}
      Edge(int vv, int rr, int ccap, int ccost):v(vv),rev(rr),cap(ccap),cost(ccost){}
   };
   int size;
   vector<vector<Edge> > edge;
   MCMF(){}
   MCMF(int s):size(s){ edge.resize(s +  1); }
   void add_edge(int u ,int v, int cap, int cost){
      edge[u].push_back(Edge(v,edge[v].size(),cap,cost));
      edge[v].push_back(Edge(u,edge[u].size()-1,0,-cost));
   }
   int get_mcmf(int src, int sink){
      int ret = 0;
      while(1){
         queue<int> q;
         vector<int> dist(size + 1, INF);
         vector<bool> inQ(size + 1, false);
         vector<int> par(size + 1, -1), paridx(size + 1, -1);

         dist[src] = 0;
         inQ[src] = true;
         q.push(src);
         while(!q.empty()){
            int here = q.front();
            q.pop();
            inQ[here] = false;

            for(int n = 0; n <  edge[here].size(); ++n){
               int next = edge[here][n].v;
               int cap = edge[here][n].cap;
               if(cap && dist[next] > dist[here] + edge[here][n].cost){
                  dist[next] = dist[here] + edge[here][n].cost;
                  par[next] = here;
                  paridx[next] = n;
                  if(!inQ[next]){
                     inQ[next] =true;
                     q.push(next);
                  }
              }
            }
         }
         if(par[sink] == -1) break;
         int flow = INF;
         for(int i = sink; i != src; i = par[i]){
            flow = min(flow, edge[par[i]][paridx[i]].cap);
         }
         for(int i=  sink;i!=src; i= par[i]){
            edge[par[i]][paridx[i]].cap -= flow;
            edge[i][edge[par[i]][paridx[i]].rev].cap += flow;
            ret += edge[par[i]][paridx[i]].cost * flow;
         }
      }
      return ret;
   }
};
int N,P;
int a[51][51];
int src, sink;
int main(){
   scanf("%d%d",&N,&P);
   src = 0, sink = N+1;
   MCMF mcmf(N+3);
   for(int n=1;n<=N-1;n++){
      for(int m=n+1;m<=N;m++){
         scanf("%d",&a[n][m]);
      }
   }
   for(int n=1;n<=N-1;n++){
      for(int m=n+1;m<=N;m++){
         int c;
         scanf("%d",&c);
         mcmf.add_edge(n,m,a[n][m],-c);
      }
      mcmf.add_edge(n,n+1,INF,0);
   }
   mcmf.add_edge(src,1,P,0);
   mcmf.add_edge(N,sink,P,0);

   printf("%d\n",-mcmf.get_mcmf(src,sink));
   return 0;
}

smu201111192 6년 전 0

n->n+1을 연결해주는게 사람을 내려주는게 아니지 않을까요?

초기상태에는 total (버스의 총 용량)만큼 flow를 쭉 흘릴 수 있는 파이프가 준비되어있습니다 (mcmf.add_edge(n,n+1,INF,0) 만을 이용해 1->n으로 flow를 흘리면 버스의 용량만큼 보낼 수 있습니다.) 물론 이경우 손님을 태우지 않으니 얻는 이익이 없습니다.

여기서 n->m으로 가는 손님 k명을 태운다면

mcmf.add_edge(n,m,a[n][m],-c) 이 엣지를 이용해서 n->m으로 k만큼 흘리게되죠.

n->m으로 파이프(mcmf.add_edge(n,n+1,INF,0) 로 total만큼 흘릴 수 있는 상태였는데

mcmf.add_edge(n,m,a[n][m],-c) 요녀석으로 k를 흘렸으니

파이프로 흘릴 수 있는 flow는 total-k가됩니다.

매순간 파이프(mcmf.add_edge(n,n+1,INF,0)로 흘릴 수 있는 플로우의 양을 버스에 사람을 얼마나 더 태울 수 있는지로 생각하면 좋을거같네요.

mcmf.add_edge(n,m,a[n][m],-c) 로 흘린 flow는 k (n->m으로 가는 손님 k명을 태움)

mcmf.add_edge(n,n+1,INF,0) 로 n->m으로 흘릴 수 있는 flow는 total-k (버스에 사람을 total-k 명 더 태 울 수 있음)

m+1이후로는 mcmf.add_edge(n,m,a[n][m],-c) 로 흘린 flow k가 다시 돌아와서

mcmf.add_edge(n,n+1,INF,0)로 흘릴 수 있는 엣지가 다시 total 이됩니다. (n->m으로 가는 손님 k명이 m에서 내렸으니 m+1부터는 버스에 태울 수 있는 사람수가 다시 total이됨)