글 읽기 - 70%에서 시간초과가 뜨는데 ...

s7d8f9 5년 전 0

우선 네트워크 플로우를 이용하여 풀었습니다.

평소에는 배열로 하였는데 이번에는 일부로 구조체+포인터를 이용해서 구현해 보기위해 시도해보았는데

보기에 배열로 풀었을때랑 크게 다르지 않은데 70퍼쯤에서 시간초과가 납니다.

제가 생각하기에는 무한루프는 아닌데 .....

혹시 간선의 개수가 너무 많아서 생기는 문제인가요?.........

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 1005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

struct node
{
    int to, flow, capacity;
    node *dual;
    node() : node(-1, 0) {};
    node(int to_tmp, int cap) :to(to_tmp), flow(0), capacity(cap), dual(nullptr) {};
    int spare() { return capacity - flow; };
    void addflow(int flow_tmp) {
        flow += flow_tmp;
        if(dual!=nullptr)
            dual->flow -= flow_tmp;
    }
};

int n, m, a,b, st = 0, fi = 2001, total=0;
vector<node*> v[MAX*2];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        node *n0 = new node(i, 1);
        v[st].push_back(n0);
        scanf("%d", &a);
        for (int k = 1; k <= a; k++)
        {
            scanf("%d",&b);
            node *n2 = new node(b+1000, 1), *n3 = new node(i, 0);
            n2->dual = n3, n3->dual = n2;
            v[i].push_back(n2), v[b + 1000].push_back(n3);
        }
    }
    for (int i = 1; i <= m; i++)
    {
        node *n1 = new node(fi, 1);
        v[i+1000].push_back(n1);
    }
    
    queue<int> q;
    while (1)
    {
        int pre[MAX * 2];
        fill_n(&pre[0], MAX * 2, -1);
        node *pre_path[MAX * 2]={0,};
        q.push(st);
        while (!q.empty())
        {
            int tmp = q.front();
            q.pop();
            for ( node *e:v[tmp])
            {
                int next = e->to;
                if (pre[next] == -1 && e->spare() > 0)
                {
                    q.push(next);
                    pre[next] = tmp;
                    pre_path[next]=e;
                    if(next==fi)
                    {
                        while(!q.empty())
                            q.pop();
                        break;
                    }
                }
            }
        }
        if(pre[fi]==-1)
            break;
        for(int i=fi; i!=st; i=pre[i])
            pre_path[i]->addflow(1);
        total++;
    }
    printf("%d",total);
    return 0;
}

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

문제

문제

출처

ICPC

70%에서 시간초과가 뜨는데 ...

s7d8f9 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말