[BOJ 8898] 스포츠 전문 채널 GSK

 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를 돌려주면 해결됩니다.

코드 )

// 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]<0) return 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;
}