글 읽기 - 네트워크 플로우 관련해서 질문합니다

jihoon 7년 전 0

https://www.slideshare.net/mobile/KuoE0/acmicpc-di... 을 참고하여 구현하였습니다.

그런데 다른 사람들에 비해 실행 시간이 지나치게 느린 것 같습니다.

제가 알고리즘을 잘못 이해해서 구현했을 수도 있겠지만 아무리 찾아봐도 어디를 비효율적으로 구현했는지 모르겠어서 질문드립니다.

답변해주시면 감사하겠습니다.

#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#define inf 2100000000
using namespace std;

class edge{
public:
    int from,to,flow,next;
};

const int maxn = 5000;

vector<edge> graph;
int last[maxn+1];

namespace maxflow{
    queue<int> q;
    stack<int> stk;
    int n;
    int lvl[maxn+1];
    int visited[maxn+1];
    int source,sink;
    void buildlgraph(){
        int now,target;
        for(int i=0;i<n;i++) lvl[i]=inf;
        lvl[source]=0;q.push(source);
        while(!q.empty()){
            now=q.front();q.pop();
            for(int i=last[now];i>=0;i=graph[i].next){
                if(!graph[i].flow) continue;
                if(lvl[graph[i].to]^inf) continue;
                target=graph[i].to;
                lvl[target]=lvl[now]+1;
                q.push(target);
            }
        }
        /*
        for(int i=0;i<n;i++) printf("%d ",lvl[i]);
        printf("\n");
        */
    }
    int blockingflow(int now,int pedge,int lim){
        if(!lim) return 0;
        int res = 0;
        visited[now]=1;
        if(now!=sink){
            for(int i=last[now];i>=0;i=graph[i].next){
                if(!graph[i].flow) continue;
                if(visited[graph[i].to]) continue;
                if(lvl[graph[i].to]==lvl[now]+1){
                    res += blockingflow(graph[i].to,i,min(lim-res,graph[i].flow));
                    if(lim==res) break;
                }
            }
        }else res = lim;
        visited[now]=0;
        if(pedge>=0){
            graph[pedge].flow -= res;
            graph[pedge^1].flow += res;
        }
        return res;
    }
    int dinic(int sz,int src,int snk){
        int res=0;n=sz;source=src;sink=snk;
        while(1){
            buildlgraph();
            if(lvl[sink]^inf) res += blockingflow(0,-1,inf);
            else break;
        }
        return res;
    }
};

void BEDGE(int ii,int from,int to,int flow){
    edge imsi;
    imsi.from=from;imsi.to=to;imsi.flow=flow;imsi.next=last[from];graph.push_back(imsi);
    imsi.from=to;imsi.to=from;imsi.flow=0;imsi.next=last[to];graph.push_back(imsi);
    last[from]=ii*2;last[to]=ii*2+1;
}

int main(){
    int edgecnt=0;
    int n,m,k;
    int aa,bb;
    scanf("%d %d %d",&n,&m,&k);
    for(int i=0;i<n+m+3;i++){
        last[i]=-1;
    }
    for(int i=1;i<=n;i++) BEDGE(edgecnt++,0,i,1);
    for(int i=1;i<=n;i++) BEDGE(edgecnt++,n+m+2,i,k);
    BEDGE(edgecnt++,0,n+m+2,k);
    for(int i=n+1;i<=n+m;i++) BEDGE(edgecnt++,i,n+m+1,1);
    for(int i=1;i<=n;i++){
        scanf("%d",&aa);
        for(int j=0;j<aa;j++){
            scanf("%d",&bb);
            BEDGE(edgecnt++,i,n+bb,1);
        }
    }
    /*
    BEDGE(edgecnt++,0,1,30);
    BEDGE(edgecnt++,0,6,10);
    BEDGE(edgecnt++,1,2,15);
    BEDGE(edgecnt++,1,4,5);
    BEDGE(edgecnt++,2,3,10);
    BEDGE(edgecnt++,2,5,10);
    BEDGE(edgecnt++,3,9,15);
    BEDGE(edgecnt++,4,5,5);
    BEDGE(edgecnt++,4,7,5);
    BEDGE(edgecnt++,5,9,7);
    BEDGE(edgecnt++,6,4,5);
    BEDGE(edgecnt++,6,8,5);
    BEDGE(edgecnt++,7,9,10);
    BEDGE(edgecnt++,8,7,6);
    */
    printf("%d",maxflow::dinic(n+m+3,0,n+m+1));
}

nisroeld99 7년 전 0

열혈강호같은 문제는 edge 구현할 필요가없기때문에(일을 할수 있는지 없는지 1,0 이기때문에)

알고리즘이름이 기억이 안나는데

bool 형으로 간단하게 구현이 가능합니다 (더 빠릅니다)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

네트워크 플로우 관련해서 질문합니다

jihoon 7년 전 0

nisroeld99 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말