백준 13992 Delight for a Cat
https://www.acmicpc.net/problem/13992
전혀 그렇게 보이지 않지만 MCMF 문제입니다… 그래프 모델링을 어떻게 할 수 있는지 살펴보도록 하겠습니다. MCMF 알고리즘은 여기서 보실 수 있습니다.
고양이가 잠을 자는 것을 base로 생각합시다. 우리는 고양이가 먹는 날만 고려하면 됩니다.
[변수 정리]
k: 주기
mn:고양이가 주기동안 먹어야 하는 최소 횟수(me),
mx: 고양이가 주기동안 먹어야 하는 최대 횟수(k-ms),
sc[i]: 고양이가 먹었을 때 느끼는 행복값,
ec[i]: 고양이가 잘 때 느끼는 행복값,
dif[i]=-(ec[i]-sc[i]): -(잠을 포기하고 먹을 때 느끼는 행복값)
[문제 세분화]
1. $ mn=mx=1 $ 인 경우
고양이가 주기 동안 한 번 식사할 수 있으므로 점화식을 구할 수 있습니다.
$ f(i)=max(f(i+1),f(i+k)-(-dif[i])) $
2. $ mn=0, 0 \leq mx $ 인 경우
주기(k) 동안 최대 mx개의 칸을 선택할 수 있을 떄 선택하는 방법의 문제와 동일합니다.
아직까지는 플로우 문제라고 유추가 되네요. ㅎㅎ.. src에서 mx의 유량을 흘려주고 각각의 유량들 중에서 최단거리(-dif)를 찾으면 됩니다. -dif를 cost로 하는 MCMF입니다.
[그래프 모델링]
Edge(capacity, cost)
A. 0(src1)에서 1(src2)로 Edge(mx,0) 연결
B. src2(1)에서 (2 … k+1)로 Edge(mx,0) 연결
C. i(2 … n-k+1)에서 i+k로 Edge(1,dif[i]) 연결
D. i(n-k+2 … n+1)에서 n+2(synk)로 Edge(1,dif[i]) 연결
E. i(2 … n+1) 에서 i+1 로 Edge(mx,0) 연결
3. $ 0 \leq mn,mx $ 인 경우
mx개의 유량이 흐르되 주기 안에서 mn 미만의 유량이 흐르는 것을 방지해야 합니다. 그래프 모델링만 바꿔서 해결할 수 있을까요? 해결할 수 있습니다!
E 간선에서 Edge(mx-mn,0) 을 연결해 봅시다. 자는 날짜가 최대 mx-mn으로 한정되기 때문에 먹는 날짜가 최소 mn으로 한정됩니다.
[최종 그래프 모델링]
A. 0(src1)에서 1(src2)로 Edge(mx,0) 연결
B. src2(1)에서 (2 … k+1)로 Edge(mx,0) 연결
C. i(2 … n-k+1)에서 i+k로 Edge(1,dif[i]) 연결
D. i(n-k+2 … n+1)에서 n+2(synk)로 Edge(1,dif[i]) 연결
E. i(2 … n+1) 에서 i+1 로 Edge(mx-mn,0) 연결
따라서 답은 (잠만 잤을 때 얻는 행복도-mcmf로 구해준 행복도의 총합)이 됩니다.
참고로, 경로는 먹는 간선인 C,D에 ID(3)을 붙인 후 C,D 간선에서 역간선의 플로우로 확인했습니다.
#include<bits/stdc++.h>
#define INF (ll)1e18
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int SZ=1005;
ll sc[SZ];
ll ec[SZ];
ll dif[SZ];
ll eat[SZ];
struct MCMF{
struct Edge{
int to,rev,id; ll cap,cost;
Edge(int to, int rev, int id, ll cap, ll cost):to(to),rev(rev),id(id),cap(cap),cost(cost){
}
};
vector<vector<Edge>> graph;
vector<pii> par;
int n,src,snk;
MCMF(int n, int src, int snk):n(n),src(src),snk(snk){
graph.resize(n+5);
par.resize(n+5);
}
void push_edge(int a, int b, int id, ll capa, ll cst){
graph[a].pb(Edge(b,graph[b].size(),id,capa,cst));
graph[b].pb(Edge(a,graph[a].size()-1,id,0,-cst));
}
bool SPFA(){
vector<int> inq;
vector<ll> dst;
inq.resize(n+5,0);
dst.resize(n+5,INF);
queue<int> q;
q.push(src); inq[src]=1; dst[src]=0;
while(!q.empty()){
int h=q.front(); q.pop();
inq[h]=0;
for(int i=0;i<(int)graph[h].size();i++){
auto e=graph[h][i];
if(e.cap<=0) continue;
if(dst[h]<INF && dst[e.to]>dst[h]+e.cost){
dst[e.to]=dst[h]+e.cost; par[e.to]={h,i};
if(inq[e.to]==0){
q.push(e.to);
inq[e.to]=1;
}
}
}
}
return dst[snk]!=INF;
}
ll flow(int k){
ll tot=0;
while(SPFA()){
ll c=0, f=INF;
for(int i=snk;i!=src;i=par[i].ff){
auto &e=graph[par[i].ff][par[i].ss];
f=min(f,e.cap);
c+=e.cost;
}
tot+=c*f;
for(int i=snk;i!=src;i=par[i].ff){
auto &e=graph[par[i].ff][par[i].ss];
e.cap-=f;
graph[e.to][e.rev].cap+=f;
}
}
for(int i=k+2;i<=n+1;i++){
for(auto e:graph[i]){
if(e.id!=3) continue;
if(e.to==i-k && e.cap>0){
eat[e.to]=1;
}
}
}
for(auto e:graph[snk]){
if(e.id!=3) continue;
if(e.cap>0){
eat[e.to]=1;
}
}
return tot;
}
};
int main(void){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n,k,ms,me; cin>>n>>k>>ms>>me;
int mn=me,mx=k-ms;
ll ans=0;
for(int i=2;i<=n+1;i++){
ll x; cin>>x;
sc[i]=x;
ans+=x;
}
for(int i=2;i<=n+1;i++) cin>>ec[i];
for(int i=2;i<=n+1;i++) dif[i]=sc[i]-ec[i];
MCMF mf=MCMF(n,0,n+2);
mf.push_edge(mf.src,1,1,mx,0);
for(int i=2;i<=k+1;i++) mf.push_edge(1,i,2,INF,0);
for(int i=2;i<=n+1;i++){
int nxt=i+k>n+1?n+2:i+k;
mf.push_edge(i,nxt,3,1,dif[i]);
}
for(int i=2;i<=n+1;i++) mf.push_edge(i,i+1,4,mx-mn,0);
cout<<ans-mf.flow(k)<<'\n';
for(int i=2;i<=n+1;i++){
if(eat[i]) cout<<"E";
else cout<<"S";
}
return 0;
}
