글 읽기 - 혹시 반례를 알 수 있을까요 ㅜ

lexio 7년 전 0

랜덤하게 2천개 테스트 케이스 만들어서

정답코드랑 실행 결과 비교해본결과 전부 동일했는데

(전부 N 10000, W 10000인 경우로 시험)

고려 못한 부분이 어떤 부분인지 알고 싶습니다... ㅜㅜ

소대를 2명이상 투입 가능한곳을 이분그래프로 만든 후 이분매칭으로 풀었습니다.

25%에서 틀렸습니다 뜨네요

#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

struct edge
{
    int v, r;
    bool m;
};

const int MAXN = 10000;
const int MAXGRAPH = 20001;
const unsigned int __INFINITY = 0xFFFFFFFF;

int N, W, T, graphSize; // T는 0 고정
int area[20000]; // bipartiteGraph 구축에 사용
bool visit[20000]; // bipartiteGraph 구축에 사용
bool inserted[20000]; // bipartiteGraph 구축에 사용
bool endConnected[20000];
int graphIndex[20000]; // bipartiteGraph에서 자기 자신의 index

unsigned int dist[MAXGRAPH]; // dinic에 사용, dist!!
int last[MAXGRAPH]; // dinic에 사용, 마지막으로 방문한 node
bool matching[MAXGRAPH]; // dinic에 사용, 매칭 됬는지 여부
vector<edge> graph[MAXGRAPH]; // dinic에 사용

void debugPrintGraph(vector<int> &g);
int process();
bool makeBipartiteGraph(vector<int> &g, int index);
bool checkAndInputEdge(queue<int> &q, int y1, int x1, int y2, int x2);
int getGraphIndex(int i);
int dinic(vector<int> &g);
bool dinicBFS(vector<int> &g);
bool dinicDFS(int index);
inline void insertEdge(int u, int v)
{
    edge e1, e2;
    
    e1.v = v;
    e1.r = graph[v].size();
    e1.m = false;
    
    e2.v = u;
    e2.r = graph[u].size();
    e2.m = true;
    
    graph[u].push_back(e1);
    graph[v].push_back(e2);
}
// 그래프를 동적으로 index 적게 사용하여, 초기화에 걸리는 과부화 줄여야 함
// -> SINK 0으로 고정, 동적으로 방문한 순서대로 인덱스 부여하기!

int main()
{
    int t, i, j;
    
	setbuf(stdout, NULL);
    
    for(scanf("%d", &t); t--;)
    {
        memset(visit, 0x00, sizeof(bool) * (MAXN + N));
        memset(inserted, 0x00, sizeof(bool) * (MAXN + N));
        memset(endConnected, 0x00, sizeof(bool) * (MAXN + N));
        memset(graphIndex, 0x00, sizeof(int) * (MAXN + N));
        scanf("%d %d", &N, &W);
        if(N > 1)
        {
            for(i = 0; i < 2; i++)
            {
                for(j = 0; j < N; j++)
                {
                    scanf("%d", area + (i * MAXN + j));
                }
            }
            
            printf("%d\n", 2 * N - process());
        }
        else
        {
            scanf("%d %d", area, area + 1);
            printf("%d\n", area[0] + area[1] <= W ? 1 : 2);
        }
    }
    
    return 0;
}

int process()
{
    int i, j, k;
    int result = 0;
    vector<int> g;
    
    for(i = 0; i < 2; i++)
    {
        for(j = 0; j < N; j++)
        {
            if(makeBipartiteGraph(g, i * MAXN + j))
            {
                //printf("makeBipartiteGraph success\n");
                //debugPrintGraph(g);
                result += dinic(g);
    
                for(k = 0; k <= graphSize; k++) graph[k].clear();
                graphSize = 0;
                g.clear();
            }
        }
    }
    
    return result;
}

void debugPrintGraph(vector<int> &g)
{
    int i, j;
    for(i = 0; i <= graphSize; i++)
    {
        printf("[%d] => ", i);
        for(j = 0; j < graph[i].size(); j++)
        {
            printf("(%d, %s) ", graph[i][j].v, graph[i][j].m ? "back" : "front");
        }
        printf("\n");
    }
    printf("index of U : ");
    for(i = 0; i < g.size(); i++)
    {
        printf("%d ", g[i]);
    }
    printf("\n");
}

bool makeBipartiteGraph(vector<int> &g, int index)
{
    queue<int> q;
    int i, j, k, t;
    bool flag;
    if(visit[index]) return false;
    visit[index] = true;
    
    q.push(index);
    while(!q.empty())
    {
        t = q.front();
        q.pop();
        
        i = t / MAXN;
        j = t % MAXN;
        
        //printf("visit (%d, %d)\n", i, j);
        
        flag = false;
        
        k = (j + 1) % N;
        if(checkAndInputEdge(q, i, j, i, k)) flag = true;
        k = (i + 1) % 2;
        if(checkAndInputEdge(q, i, j, k, j)) flag = true;
        k = j - 1 < 0 ? N - 1 : j - 1;
        if(checkAndInputEdge(q, i, j, i, k)) flag = true;
        
        if(flag)
        {
            g.push_back(graphIndex[i * MAXN + j]);
            inserted[i * MAXN + j] = true;
        }
    }
    
    return g.size() > 0;
}

inline bool checkAndInputEdge(queue<int> &q, int y1, int x1, int y2, int x2)
{
    if(area[y1 * MAXN + x1] + area[y2 * MAXN + x2] <= W)
    {
        if(!visit[y2 * MAXN + x2])
        {
            q.push(y2 * MAXN + x2);
            visit[y2 * MAXN + x2] = true;
        }
        
        if(!inserted[y1 * MAXN + x1])
        {
            insertEdge(getGraphIndex(y1 * MAXN + x1), getGraphIndex(y2 * MAXN + x2));
            if(!endConnected[y2 * MAXN + x2])
            {
                insertEdge(getGraphIndex(y2 * MAXN + x2), T);
                endConnected[y2 * MAXN + x2] = true;
            }
            
            inserted[y2 * MAXN + x2] = true;
            return true;
        }
    }
    
    return false;
}

inline int getGraphIndex(int i)
{
    if(!graphIndex[i]) graphIndex[i] = ++graphSize;
    return graphIndex[i];
}

int dinic(vector<int> &g)
{
    int result = 0, i;
    
    memset(matching, 0x00, sizeof(bool) * (graphSize + 1));
    
    while(dinicBFS(g))
    {
        memset(last, 0x00, sizeof(int) * (graphSize + 1));
        for(i = 0; i < g.size(); i++)
        {
            if(!matching[g[i]] && dinicDFS(g[i]))
            {
                result++;
            }
        }
    }
    
    return result;
}

bool dinicBFS(vector<int> &g)
{
    queue<int> q;
    int i, j;
    memset(dist, 0xFF, sizeof(unsigned int) * (graphSize + 1));
    
    for(i = 0; i < g.size(); i++)
    {
        if(!matching[g[i]])
        {
            q.push(g[i]);
            dist[g[i]] = 0;
        }
    }
    
    while(!q.empty())
    {
        i = q.front();
        q.pop();
        
        for(j = 0; j < graph[i].size(); j++)
        {
            edge &e = graph[i][j];
            if(!e.m && dist[e.v] == __INFINITY && dist[i] < dist[T])
            {
                dist[e.v] = dist[i] + 1;
                q.push(e.v);
            }
        }
    }
    
    return dist[T] != __INFINITY;
}

bool dinicDFS(int index)
{
    if(index == T) return true;
    
    for(int &i = last[index]; i < graph[index].size(); i++)
    {
        edge &e = graph[index][i];
        
        if(!e.m && dist[e.v] == dist[index] + 1 && dinicDFS(e.v))
        {
            matching[index] = true;
            e.m = true;
            graph[e.v][e.r].m = false;
            return true;
        }
    }
    
    return false;
}

portableangel 7년 전 2

N이 홀수인 경우로 테스트해보세요

N이 홀수일 경우 패리티가 맞지 않아 이분 그래프가 아니게 됩니다

lexio 7년 전 0

오 감사합니다 이분매칭으로 안되는거였군요 ㅜ

lexio 7년 전 0

7 100

7 9 84 70 5 32 11

84 31 65 7 59 27 24

여기서 한점이 방문 순서에 따라 U에 속할 수 도 V에 속할 수 도 있는 문제가 발생하네요 ㅜ

djm03178 6년 전 0

헉 감사합니다 이 예시 덕분에 오답 원인을 찾았습니다 ㅠㅠ

joonas 3년 전 0

감사합니다... 이분 그래프로 한참을 비볐는데 ㅠㅠ

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

문제

문제

출처

ICPC

혹시 반례를 알 수 있을까요 ㅜ

lexio 7년 전 0

portableangel 7년 전 2

lexio 7년 전 0

lexio 7년 전 0

djm03178 6년 전 0

joonas 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말