문제 링크 : https://www.acmicpc.net/problem/2544 (P1)
문제 태그
문제 풀이
맨처음에 이 문제를 볼 때는 DP가 생각났다. 상태를 잘 정의해서 풀면 $O(N^3)$에 문제를 해결할 수 있을 것 처럼 보였다. 하지만 다음 상태로 넘어가는 그 관계에 대해서 정의를 하는 것이 힘들어서 다른 방법을 찾았다.
위의 과정에서 생각을 하면서 이 문제를 좀 그리디하게 접근할 수 있다는 것을 깨달았다. 당연히 가장 높은 수를 없애는 방향으로 줄을 지워야 한다. 결국 가장 높은 수부터 k개의 줄을 이용해 어느 수 까지 없앨 수 있는 지를 알아야 한다.
가능한 최소(최대) 를 구하는 문제가 나온 이상, 결정론적으로 문제를 바꿔서 생각을 안해볼 수가 없다. 이 문제를 결정론적으로 바꾸면 격자판 내의 q이상의 모든 수를 k줄 내에 포함시킬 수 있는지를 판별하는 문제가 된다. 이는 이 문제 와 동일한 문제가 된다.
q이상의 모든 수를 k줄 내에 포함시킬 수 있는지를 판별하는 문제는 최소 버텍스 커버로, 이분그래프에서는 이분 매칭으로 풀 수 있음이 알려져 있다. 물론 이 문제와 같은 경우에는 마지막에 추가로 역추적까지 진행을 해주어야 한다.
코드
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll arr[3030][3030];
ll n,m,t,cnt,acnt,bcnt;
ll vis[3030];
ll rev[3030];
ll chk[3030];
ll b[3030];
vector<ll> v[1005];
bool dfs(ll u){
if(vis[u]==cnt)return 0;
vis[u]=cnt;
for(auto k:v[u]){
if(rev[k]==0 || dfs(rev[k])){
rev[k]=u;
return 1;
}
}
return 0;
}
ll bm(){
ll ret=0;
for(cnt=1;cnt<=n;cnt++){
if(dfs(cnt)){
ret++;
chk[cnt]=1;
}
}
return ret;
}
void dfs2(ll u){
if(vis[u]==0)return;
vis[u]=0;
acnt++;
for(auto k:v[u])bcnt+=!b[k]++, dfs2(rev[k]);
}
ll sol (ll k) {
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
if(arr[i][j]>=k)
v[i].push_back(j);
return bm();
}
vector<ll> v2;
int main(){
ll i,j,k,l;
scanf("%lld %lld %lld",&n,&m,&k);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf("%lld",&arr[i][j]);
v2.push_back(arr[i][j]);
}
v2.push_back(0);
sort(v2.begin(),v2.end());
v2.erase(unique(v2.begin(), v2.end()),v2.end());
ll lo=0,hi=v2.size();
v2[hi]=1e18;
while(lo<hi){
ll mid=(lo+hi)/2;
ll x=v2[mid];
ll ans=sol(x);
//printf("%lld %lld %lld %lld\n",lo,mid,hi,ans);
if(ans<=k) hi=mid;
else lo=mid+1;
for(i=1;i<=303;i++){
v[i].clear();
chk[i]=0;
vis[i]=0;
b[i]=0;
rev[i]=0;
}
}
if(hi==0) printf("0");
else printf("%lld",v2[hi-1]);
ll fin=v2[hi];
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
if(arr[i][j]>=fin)
v[i].push_back(j);
bm();
for(int i=1;i<=n;i++)
if(!chk[i])
dfs2(i);
ll bon=k-(n-acnt+bcnt);
ll ans1=min(n-acnt+bon,n);
ll bon2=k-(ans1+bcnt);
ll ans2=bon2+bcnt;
printf("\n%lld",ans1);
for(int i=1;i<=n;i++){
if(vis[i]!=0)printf(" %lld",i);
else if(bon){
bon--;
printf(" %lld",i);
}
}
printf("\n%lld",ans2);
for(int i=1;i<=m;i++){
if(b[i])printf(" %lld",i);
else if(bon){
bon--;
printf(" %lld",i);
}
}
}
|