http://poj.org/problem?id=3422
http://hos.ac/slides/20150319_flow.pdf
ここのp69に載っている問題と同じ。
負辺があるが、グラフが特殊な形をしているので、dijkstraで求めても最短経路が求まり、ポテンシャルも正しく求まる。
これではつまらないので負辺を取り除く方法を考えた。
http://snuke.hatenablog.com/entry/2017/06/07/115821
上のすぬけさんのブログと蟻本を参考にした。
言い換えると今解きたい問題は、dv(s)=-K, dv(t)=K,それ以外dv(v)=0の時の最小費用循環流問題なので、
スーパーノードS,Tを作り、そこから適切にsやtに辺を張ることで実現できる。
これでもACが取れましたといいたいところだが、辺が増えすぎてTLEした。
負辺を含む最小費用流について(Attack the Moles) - sigma425のブログ
ここに書いてあるが、今している変形はこのブログの3に相当し、FがNくらい増えて、オーダーが悪くなることがわかる。
ACしたの
int N, K;
int main() {
scanf("%d%d", &N, &K);
int s = 0, t = N * N * 2 - 1;
MCF::init(N * N * 2);
rep(i, 0, N) {
rep(j, 0, N) {
int id = i * N + j;
int a; scanf("%d", &a);
MCF::add_edge(id, id + N * N, 1, -a);
MCF::add_edge(id, id + N * N, K, 0);
if(i != N - 1) {
MCF::add_edge(id + N * N, id + N, K, 0);
}
if(j != N - 1) {
MCF::add_edge(id + N * N, id + 1, K, 0);
}
}
}
printf("%d\n", -MCF::get(s, t, K));
return 0;
}
負辺を取り除いたの(TLE)
namespace MCC {
struct edge { int to, cap, cost, rev; };
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];
int S[MAX_V];
int off;
void init(int v) {
V = v;
}
void add_edge(int from, int to, int cap, int cost) {
if(cost >= 0) {
G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
G[to].push_back((edge){from, 0, -cost, (int)G[from].size() - 1});
}
else {
off += cap * cost;
S[from] += cap; S[to] -= cap;
G[to].push_back((edge){from, cap, -cost, (int)G[from].size()});
G[from].push_back((edge){to, 0, cost, (int)G[to].size() - 1});
}
}
void set_d(int v, int d) { S[v] += d; }
int impl(int s, int t, int f) {
int res = 0;
memset(h, 0, sizeof(h));
while(f > 0) {
priority_queue<pi, vector<pi>, greater<pi> > que;
fill(dist, dist + V, inf);
dist[s] = 0;
que.push(pi(0, s));
while(!que.empty()) {
pi p = que.top(); que.pop();
int v = p.sec;
if(dist[v] < p.fst) continue;
rep(i, 0, (int)G[v].size()) {
edge &e = G[v][i];
if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
que.push(pi(dist[e.to], e.to));
}
}
}
if(dist[t] == inf) return -1;
rep(v, 0, V) h[v] += dist[v];
int d = f;
for(int v = t; v != s; v = prevv[v]) {
d = min(d, G[prevv[v]][preve[v]].cap);
}
f -= d;
res += d * h[t];
for(int v = t; v != s; v = prevv[v]) {
edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
}
int get() {
int f = 0;
int s = V, t = V + 1;
rep(i, 0, V) {
if(S[i] > 0) add_edge(i, t, S[i], 0);
if(S[i] < 0) {
add_edge(s, i, -S[i], 0);
f += -S[i];
}
}
V += 2;
return impl(s, t, f) + off;
}
}
int N, K;
int main() {
scanf("%d%d", &N, &K);
int s = 0, t = N * N * 2 - 1;
MCC::init(N * N * 2);
MCC::set_d(s, -K);
MCC::set_d(t, K);
rep(i, 0, N) {
rep(j, 0, N) {
int id = i * N + j;
int a; scanf("%d", &a);
MCC::add_edge(id, id + N * N, 1, -a);
MCC::add_edge(id, id + N * N, K, 0);
if(i != N - 1) {
MCC::add_edge(id + N * N, id + N, K, 0);
}
if(j != N - 1) {
MCC::add_edge(id + N * N, id + 1, K, 0);
}
}
}
printf("%d\n", -MCC::get());
return 0;
}
