http://poj.org/problem?id=1486
完全マッチングに必ず使われる辺を答えればよい。
それはフローが流れた辺を削除したとき完全マッチングになるかどうかで判断すればよい。
その際に押し戻すテクを使ってN-1のフローを作り、対象の辺の容量を0にしてdfsすると高速。
フローのライブラリを少しいじるだけでできる。
フローに限らず再帰の引数でバグらせがちなので注意。特にデフォルトの値を設定するとき。
int S[MAX_N], T[MAX_N];
namespace MF {
struct edge {int to, cap, rev; };
vector<edge> G[MAX_N];
bool used[MAX_N];
void init(int n) {
rep(i, 0, n) G[i].clear();
memset(used, 0, sizeof(used));
}
int add_edge(int from, int to, int cap) {
G[from].push_back((edge){to, cap, (int)G[to].size()});
G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
return (int)G[from].size() - 1;
}
int dfs(int v, int t, int f, bool change = true) {
if(v == t) return f;
used[v] = true;
for(int i = 0; i < (int)G[v].size(); i++) {
edge &e = G[v][i];
if(!used[e.to] && e.cap > 0) {
int d = dfs(e.to, t, min(f, e.cap), change);
if(d > 0) {
if(change) {
e.cap -= d;
G[e.to][e.rev].cap += d;
}
return d;
}
}
}
return 0;
}
ll get(int s, int t) {
ll flow = 0;
while(true) {
memset(used, 0, sizeof(used));
int f = dfs(s, t, inf);
if(f == 0) return flow;
flow += f;
}
}
bool ok(int v, int k, int n) {
int s = 2 * n, t = 2 * n + 1;
int u = G[v][k].to, rev = G[v][k].rev;
G[u][rev].cap = 0;
swap(G[s][S[v]].cap, G[G[s][S[v]].to][G[s][S[v]].rev].cap);
swap(G[u][T[u]].cap, G[G[u][T[u]].to][G[u][T[u]].rev].cap);
bool res = true;
memset(used, 0, sizeof(used));
if(dfs(s, t, inf, false)) res = false;
G[u][rev].cap = 1;
swap(G[s][S[v]].cap, G[G[s][S[v]].to][G[s][S[v]].rev].cap);
swap(G[u][T[u]].cap, G[G[u][T[u]].to][G[u][T[u]].rev].cap);
return res;
}
}
int N;
int X1[MAX_N], Y1[MAX_N], X2[MAX_N], Y2[MAX_N];
int X[MAX_N], Y[MAX_N];
vector<pi> ans;
int main() {
for(int q = 1; ; q++) {
scanf("%d", &N);
if(N == 0) break;
rep(i, 0, N) scanf("%d%d%d%d", &X1[i], &X2[i], &Y1[i], &Y2[i]);
rep(i, 0, N) scanf("%d%d", &X[i], &Y[i]);
int s = 2 * N, t = 2 * N + 1;
MF::init(2 * N + 2);
ans.clear();
rep(i, 0, N) {
rep(j, 0, N) {
if(X1[i] <= X[j] && X[j] <= X2[i] && Y1[i] <= Y[j] && Y[j] <= Y2[i]) {
MF::add_edge(i, j + N, 1);
}
}
}
rep(i, 0, N) {
S[i] = MF::add_edge(s, i, 1);
T[i + N] = MF::add_edge(i + N, t, 1);
}
bool ok = true;
if(MF::get(s, t) != N) ok = false;
if(ok) {
rep(i, 0, N) {
rep(j, 0, (int)MF::G[i].size()) {
MF::edge e = MF::G[i][j];
if(e.cap == 0) {
if(MF::ok(i, j, N)) ans.push_back(pi(i, e.to));
}
}
}
}
printf("Heap %d\n", q);
if(ok && (int)ans.size() > 0) {
rep(i, 0, (int)ans.size()) {
printf("(%c,%d)%c", ans[i].fst + 'A', ans[i].sec - N + 1, i == (int)ans.size() - 1 ? '\n' : ' ');
}
}
else printf("none\n");
printf("\n");
}
return 0;
}
outputの形式がややこしい。問題文は読みましょう。
