zipbob   7달 전

종만북을 보면서 네트워크 플로우에 대해 공부중입니다.

열혈강호1문제같은 경우는 이분매칭으로 해결하였지만

열혈강호2 문제는 한 사람이 2가지 일을 할 수 있어서

포드 폴커슨으로 해결하려고 하였습니다.

source는 0 

사람 1~n

일 n+1~n+m

sink n+m+1

 source -사람 2

사람-일 1

일-sink 1

로 가중치를 두고 구현해보았는데 시간초과뜨네요 무슨 문제인가요 ?  잘못된 부분이나 더 좋은 알고리즘 있으면 알려주시면 감사하겠습니다.

코드는 종만북 참고하였습니다.

exqt   7달 전

저도 참고해서 풀었는데 시간초과 나더군요 ㅠㅠ

23번째 줄 인접리스트 벡터로 구현하셔서 간선 없는 부분 빼면 좀 빠르게 나와요

zipbob   7달 전

이렇게 써두 시간초과네요 ㅜㅜ

exqt   7달 전

#include <bits/stdc++.h>
using namespace std;
 
#define in cin
#define out cout
 
#define REP(i,n) for(int i=0; i<n; i++)
#define REP2(i,s,e) for(int i=s; i<e; i++)
#define REPE(i,s,e) for(int i=s; i<=e; i++)
#define REPR(i,s,e) for(int i=s; i>=e; i--)
 
#define all(v) v.begin(), v.end()
#define pb push_back
 
#define ll long long
#define pii pair<int, int>
 
#define X first
#define Y second
#define intINF 2147483647
#define llINF 9223372036854775807LL
#define MOD 1000000007
 
#define rd(n) scanf("%d", &n)
#define rdll(n) scanf("%lld", &n)
 
const int MAX_V = 2010;
const int INF = intINF;
 
class flowNetwork
{
private:
    int V;
 
    int cap[MAX_V][MAX_V];
    int flow[MAX_V][MAX_V];
    vector<int> adj[MAX_V];
 
public:
    void init(int n)
    {
        memset(cap, 0, sizeof(cap));
        V = n;
    }
 
    void addEdge(int x, int y, int c)
    {
        cap[x][y] += c;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
 
    int get(int src, int sink)
    {
        memset(flow, 0, sizeof(flow));
        int totalFlow = 0;
 
         
        while(true)
        {
            int parent[MAX_V];
            memset(parent, -1, sizeof(parent));
 
            queue<int> Q;
 
            parent[src] = src;
            Q.push(src);
 
            while(Q.size() && parent[sink] == -1)
            {
                int here = Q.front(); Q.pop();
                for(int i = 0; i < adj[here].size(); i++)
                {
                    int there = adj[here][i];
                    if(cap[here][there] - flow[here][there] > 0 &&
                        parent[there] == -1)
                    {
                        Q.push(there);
                        parent[there] = here;
                    }
                }
            }
 
            if(parent[sink] == -1) break;
 
            int amount = INF;
            for(int p = sink; p != src; p = parent[p])
            {
                amount = min(amount,
                        cap[parent[p]][p] - flow[parent[p]][p]);
            }
 
            for(int p = sink; p != src; p = parent[p])
            {
                flow[parent[p]][p] += amount;
                flow[p][parent[p]] -= amount;
            }
 
            totalFlow += amount;
        }
 
        return totalFlow;
    }
};
 
int main()
{
    int n, m; rd(n); rd(m);
    // 0 : src
    // 1~n
    // n+1 ~ n+m
    // n+m+1 sink
 
    flowNetwork G;
    G.init(n+m+10);
 
    REPE(i, 1, n)
    {
        G.addEdge(0, i, 2);
    }
    REPE(i, 1, m)
    {
        G.addEdge(n+i, n+m+1, 1);
    }
 
    REPE(i, 1, n)
    {
        int k; rd(k);
        REP(j, k)
        {
            int x; rd(x);
            G.addEdge(i, n+x, 1);
        }
    }
 
    printf("%d", G.get(0, n+m+1));
 
    return 0;
}

저랑 다른게 없는거 같은데..

zipbob   7달 전

매크로 차이인가.... 좀 더 공부해볼게요 감사합니다.

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