티스토리 뷰

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8898에서 채점할 수 있습니다.


풀이 )

 i 경기 이후에 j 경기를 취재할 수 있는 경우, 즉, 인 경우를 ( i -> j )라고 표현하겠습니다. 그러면 이 문제를 '취재할 수 없는 가장 큰 경기의 부분집합의 크기 구하는 문제'에서, '최소한의 경기들을 삭제해서 서로 간선이 없도록 하는 문제'로 바꿀 수 있습니다. 전체 경기 수 - 삭제한 경기 수가 답이 되기 때문이지요.


 이제 다음과 같은 이분 그래프를 구성해 보겠습니다. ( i->j ) 인 경우, ( i -> n+j ) 로 간선을 그린 것입니다. (1->2), (2->3), (1->3) 의 경우입니다.




 이 그래프에서 만일 최소한의 정점 쌍(2와 n+2를 동시에 없애는 것입니다.)을 삭제해서 간선을 모두 없애는 작업을 할 수 있다면, 그게 곧 '최소한의 경기들을 삭제해서 서로 간선이 없도록 하는 문제'의 답이 되기 때문에 풀이가 끝납니다. ... (1)



 Vertex cover와 굉장히 유사하지만, 2와 n+2를 모아서 하나의 정점처럼 계산해야 하며 동시에 삭제해야 한다는 조건 때문에 차이점이 있습니다. 그런데 문제에 주어진 조건 를 사용하면 이 차이점을 0으로 만들 수 있습니다. 이 조건으로 다음과 같은 명제를 쉽게 증명할 수 있기 때문입니다. 명제 : ( i -> j) 이고, ( j-> k) 이면, (i->k)이다. 


 이분 그래프로 보면 '( i -> n+j) 이고, ( j-> n+k) 이면, (i->n+k)이다.'가 됩니다.




 이제 i 와 n+i 에 연결된 간선을 생각해보면, 위와 같이 n+i 와 연결된 정점들 i와 연결된 정점들이 서로 모두 연결되어 있음을 알 수 있습니다. 따라서 n+i 와 연결된 정점들이 전멸하거나, i와 연결된 정점들이 전멸하거나 둘 중 하나는 성립해야 합니다. 두 집합이 모두 공집합이 아니라면, 간선 1개는 무조건 살기 때문입니다.


 i와 연결된 정점들이 전멸한 경우를 생각해보겠습니다. 그러면 i는 간선이 연결되어 있지 않은 잉여 정점이 됩니다. 그렇다면, n+i정점을 삭제하는 작업을, i와 n+i 정점 두 개를 동시에 삭제하는 작업과 동일시할 수 있습니다. 물론 비용은 똑같이 1 증가한다고 했을 때 입니다.


 이런 점을 통해, 이 그래프에서 vertex cover를 돌린 결과와 (1)의 결과가 사실상 같음을 보일 수 있습니다. 따라서 아래 코드와 같이 vertex cover를 돌려주면 해결됩니다.


코드 )


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - K
// BOJ 8898 스포츠 전문 채널 GSK
 
#include <bits/stdc++.h>
using namespace::std;
 
#define INF 2140000000
#define MAX_V 3005
struct edge{        // to : 목적지, c : 용량 , r: 역변 정보 : ad[i][j] 의 역엣지 = ad[ad[i][j].to][ad[i][j].r]
    int to,c,r;  
};
 
int n;
int st[1005],en[1005];
bool can[1005][1005];
bool ans[1005];
 
vector<edge> ad[MAX_V]; // 그래프 인접리스트
bool chk[MAX_V];        // DFS에서 방문 체크
 
int level[MAX_V];
int iter[MAX_V];
 
void add_edge(int v1,int v2,int c){  // v1->v2 로 용량 c의 엣지 추가
    edge e1={v2,c,ad[v2].size()};
    ad[v1].push_back(e1);
    edge e2={v1,0,ad[v1].size()-1};
    ad[v2].push_back(e2);
}
 
void bfs(int s){                     // s로부터의 최단거리 계산
    memset(level,-1,sizeof(level));
    queue<int> q;
    level[s]=0;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int i=0;i<ad[v].size();i++){
            edge &e=ad[v][i];
            if(e.c>0 && level[e.to]<0){
                level[e.to]=level[v]+1;
                q.push(e.to);
            }
        }
    }
}
 
int dfs(int v,int t,int f){         // 증가경로를 DFS로 탐색
    if(v==t) return f;
    for(int &i=iter[v];i<ad[v].size();i++){
        edge &e=ad[v][i];
        if(e.c>0 && level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.c));
            if(d>0){
                e.c-=d;
                ad[e.to][e.r].c+=d;
                return d;
            }
        }
    }
    return 0;
}
 
int max_flow(int s,int t){       // s->t 의 최대흐름 계산
    int flow=0;
    while(true){
        bfs(s);
        if(level[t]<0return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>0){
            flow+=f;
        }
    }
}
bool chk_can(int s,int t,int op){
    return st[s]+en[s]+op<=st[t];
}
 
void input(){
    for(int i=0;i<=3000;i++) ad[i].clear();
    for(int i=0;i<=1000;i++) ans[i]=false;
    scanf("%d",&n);
    for(int i=1;i<=n;i++scanf("%d",&st[i]);
    for(int i=1;i<=n;i++scanf("%d",&en[i]);
    for(int i=1;i<=n;i++for(int j=i;j<=n;j++){
        int in;
        scanf("%d",&in);
        can[i][j]=chk_can(i,j,in);
        can[j][i]=chk_can(j,i,in);
    }
 
    for(int i=1;i<=n;i++) add_edge(0,i,1);
    for(int i=n+1;i<=2*n;i++) add_edge(i,3000,1);
    for(int i=1;i<=n;i++for(int j=n+1;j<=2*n;j++)
        if(can[i][j-n])
            add_edge(i,j,1);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        int op=max_flow(0,3000);
        memset(chk,0,sizeof(chk));
        queue<int> q;
        q.push(0);
        chk[0]=true;
        while(!q.empty()){
            int now=q.front();
            q.pop();
            for(int i=0;i<ad[now].size();i++){
                edge &next=ad[now][i];
                if(next.c>0 && !chk[next.to]){
                    chk[next.to]=true;
                    q.push(next.to);
                }
            }
        }
 
        for(int i=1;i<=n;i++if(!chk[i])  ans[i]=true;
        for(int i=1;i<=n;i++if(chk[i+n]) ans[i]=true;
        vector<int> last;
        for(int i=1;i<=n;i++if(!ans[i]) last.push_back(i);
        printf("%d\n",last.size());
        for(int i=0;i<last.size();i++){
            printf("%d ",last[i]);
            if(i+1==last.size())
                printf("\n");
        }
    }
    return 0;
}
cs


'문제 풀이' 카테고리의 다른 글

[BOJ 8911] 거북이  (0) 2018.01.22
[BOJ 8897] Slicing Tree  (0) 2018.01.11
[BOJ 8898] 스포츠 전문 채널 GSK  (0) 2018.01.11
[BOJ 8899] Square Annulus  (0) 2018.01.11
[BOJ 8890] Critical 3-Path  (0) 2018.01.11
[BOJ 8889] 등고선 지도  (0) 2018.01.11