4개의 댓글이 있습니다.
-
-
JongMan -
음 푼사람 나밖에 없나;; 일루옹 미워여 OTL
Network flow 를 이용해 특정 burden level 이 가능한가 불가능한가를 알 수 있습니다. 그럼 가능한 최소의
burden level 을 찾은 후,맨 앞사람부터 각 사람의 parent 를 고정시켜 가면서 이 경우에도 valid
assignment 가 있는지를 확인하면서 답을 만들어나가면 됩니다.
이런 문제는 답 만드는 과정이 어렵고요.. 실제로 특정 burden level 이 가능한가 여부는.. 이분매칭하듯이 이분그래프를
만들고, sink 들에서 supersink 로 연결되는 간선 capacity 를 burden level 로 두고, (a,b)
간선을 해당 소스에서 싱크로 연결하고, 각 소스에서 슈퍼싱크로 연결해서 확인하면 됩니다. 음 그림이 없으니 힘드네요. 한번
그려보세요 ㅋ
[spoiler="소스코드 보기"]~~~ cpp
#line 2 "WSNParentsAssignment.cpp"
#include
#include
#include
#include
#include
#include
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef long long ll;
const int MAXV = 200;
struct NetworkFlow
{
int flow[MAXV][MAXV], cap[MAXV][MAXV], totalFlow, V;
NetworkFlow(int V = 0): V(V) { CLEAR(cap,0); CLEAR(flow,0); totalFlow = 0; }
void clear() { CLEAR(cap,0); CLEAR(flow,0); totalFlow = 0; }
void addEdge(int a, int b, int c) { cap[a][b] += c; }
void push(int a, int b, int c) { flow[a][b] += c; flow[b][a] = - flow[a][b]; }
int res(int a, int b) { return cap[a][b] - flow[a][b]; }
int pushFlow(int source = 0, int sink = 1)
{
vectorpred(V, -1); queue q;
q.push(source); pred[source] = source;
while(!q.empty() && pred[sink] == -1)
{
int u = q.front(); q.pop();
for(int v = 0; v < V; ++v) if(res(u,v) > 0 && pred[v] == -1) { pred[v] = u; q.push(v); }
}
if(pred[sink] == -1) return 0;
int h, amt = 987654321;
h = sink; while(pred[h] != h) { amt <?= res(pred[h], h); h = pred[h]; }
h = sink; while(pred[h] != h) { push(pred[h], h, amt); h = pred[h]; }
totalFlow += amt;
return amt;
}
};
struct WSNParentsAssignment
{
int n;
vectoradj[51];
string nearest;
vectorfixed;
NetworkFlow net;
bool tryMatch(int burden)
{
net.clear();
int SRC = n*3;
int SNK = n*3+1;
REP(i,n) net.addEdge(SRC, i*2, 1);
REP(i,n) net.addEdge(i*2+1, SNK, burden);
REP(here,n) REP(i,adj[here].sz)
{
if(fixed[here] != -1 && fixed[here] != i) continue;
int there = adj[here][i];
int vertex = (there == n ? SNK : there * 2 + 1);
net.addEdge(here*2, vertex, 1);
}
while(net.pushFlow(SRC, SNK));
return net.totalFlow >= n;
}
vectorminNetworkBurdenLevel(vector network, string nearest)
{
n = network.sz;
vectorc = network;
REP(k,c.sz) REP(i,c.sz) REP(j,c.sz) if(c[i][k] == 'Y' && c[k][j] == 'Y') c[i][j] = 'Y';
REP(i,c.sz)
{
bool seen = nearest[i] == 'Y';
REP(j,c.sz) if(c[i][j] == 'Y' && nearest[j] == 'Y') { seen = true; }
if(!seen) return vector();
}
net = NetworkFlow(n*3 + 2);
REP(i,n)
{
REP(j,n)
if(network[i][j] == 'Y')
adj[i].pb(j);
if(nearest[i] == 'Y') adj[i].pb(n);
}
fixed.resize(n, -1);
int lo = 0, hi = n+1;
while(lo+1 < hi)
{
int mid = (lo+hi)/2;
if(tryMatch(mid))
hi = mid;
else
lo = mid;
}
if(hi == n+1) return vector();
printf("resulting burden %d\n", hi);
vectorret(n);
REP(i,n)
{
REP(j,adj[i].sz)
{
fixed[i] = j;
ret[i] = adj[i][j];
if(tryMatch(hi))
break;
}
}
return ret;
}
};
// Powered by FileEdit# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
17년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
JongMan
오늘의 문제는 SRM367 Hard 입니다. ^^
[문제 보러 가기]
자아 열심히 풉시다! ^ㅁ^
17년 전