글 읽기 - 정점분할과 네트워크 플로우... 틀렸습니다 원인이 뭘까요

show981111 4년 전 0

정점분할을 사용해서 각 정점을 한번씩만 방문하도록 만든뒤 경로 출력까지 잘된거 같은데 틀렸습니다가 뜨네요...

도대체 왜 틀린걸까요.....

#include <queue>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#define MAX 10001
using namespace std;
class Edge
{
public:
    int to;
    int cap;
    Edge(int a, int b) 
    {
        to = a;
        cap = b;
    }
};
vector<Edge> graph[MAX];
char flow[MAX][MAX];
int parent[MAX];

int maxflow(int start, int end)
{
   int res = 0;
   while(1)
   {
       queue<int> q;
       fill(parent, parent + MAX, -1);
       q.push(start);
       
       while(!q.empty() && parent[end] == -1)
       {
           int cur = q.front();
           q.pop();
           
           for(int k = 0; k < graph[cur].size(); k++)
           {
               int child = graph[cur][k].to;
                
               if(graph[cur][k].cap - flow[cur][child] > 0 && parent[child] == -1)
               {
                   q.push(child);
                   parent[child] = cur;
                   if(child == end) break;
               }
           }
       }
        
       if(parent[end] == -1) break;
       
       for(int a = end; a!= start; a = parent[a])
       {
           flow[parent[a]][a]++;
           flow[a][parent[a]]--;
       }
       res++;
    }
   
   return res;
}
void printway()
{
    int prev[MAX];
    stack<int> s;
   while(1)
   {
       while(!s.empty()) s.pop();
       fill(prev,prev+MAX,-1);
       queue<int> q1;
       q1.push(1);
       
       while(!q1.empty())
       {
           int cur = q1.front();
           q1.pop();
           for(int v = 0; v < graph[cur].size(); v++)
           {
               int child = graph[cur][v].to;
               if((int)flow[cur][child] == 1 && prev[child] == -1) //유량이 흐른다면!
               {
                   q1.push(child);
                   prev[child] = cur;
                   if(child == 2) break;
               }
           }
       }
       
       if(prev[2] == -1) break;
       for(int l = 2; l != 1; l = prev[l])
       {
           flow[prev[l]][l] = 0;
           flow[l][prev[l]] = 0;
           if(l % 2 == 0) 
           {
               int next = (l + 2) / 2;
               s.push(next);
           }
       }
       s.push(1);
       
       while(!s.empty())
       {
           int t = s.top();
           s.pop();
           printf("%d ", t);
           if(t == 2)
           {
               printf("\n");
           }
       }
       
   }
}
int main()
{
   int casenum = 0;
   while(1)
   {
       casenum++;
       memset(flow,0,sizeof(flow));
       int K,N;
       scanf("%d %d",&K,&N);
       if( K == 0 && N == 0) break;
       for(int i = 0; i <= N + 1; i++)
       {
           graph[i].clear();
       }
       for(int i = 1; i <= N; i++)
       {
           int ini = 2*i -2;
           int outi = 2*i - 1;
           graph[ini].push_back(Edge(outi,1));
           while(1)
           {
               int x;
               char a;
               scanf("%d%c", &x,&a);
               int ix = 2*x - 2;
               int ox = 2*x - 1;
               graph[outi].push_back(Edge(ix,1));
               graph[ix].push_back(Edge(outi,0));
               
               if(a == '\n') break;
           }
       }
       
       int total = maxflow(1,2);
       printf("Case %d:\n",casenum);
       if(total < K)
       {
           printf("Impossible\n");
       }else
       {
           printway();
           
       }
       
   }

   return 0;
}

show981111 4년 전 0

처음에 그래프를 초기화 할때, N+1 까지가 아니라 정점분할을 했으므로 최소 2*N 까지는 초기화를 해줘야합니다...

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

문제

문제

출처

ICPC

정점분할과 네트워크 플로우... 틀렸습니다 원인이 뭘까요

show981111 4년 전 0

show981111 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말