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)
//minimum cost circularation namespace MCC { //init before you use it. //negative edges ok. struct edge { int to, cap, cost, rev; }; int V; //num of vertex 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; //memset(S, 0, sizeof(S)); //rep(i, 0, V + 2) G[i].clear(); } 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() { //u,v,cap,cost 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]; } } /* rep(i, 0, V) { rep(j, 0, (int)G[i].size()) { debug(i, G[i][j].to, G[i][j].cost); } } */ 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; }