Brief description :
n 个箱子存放有 n 种物品，要求确定一种分类方案，使得移动代价最小。
Analyse :
求移动代价最小划归到计算保留在原处的物品数最大。。。然后。。。
const int N = 150;
int W[N][N], lx[N], ly[N], p[N];
bool vx[N], vy[N];
int n;
void init(){
RD(n); REP_2(i, j, n, n) RD(W[i][j]);
}
#define w(x, y) (lx[x] + ly[y] - W[x][y])
bool dfs(int x){
vx[x] = true; REP(y, n) if (!vy[y] && !w(x, y)){
vy[y] = true; if(p[y]==-1||dfs(p[y])){
p[y] = x;
return true;
}
}
return false;
}
void KM(){
FLC(p, -1); RST(lx, ly);
REP_2(i, j, n, n) checkMax(lx[i], W[i][j]);
REP(x, n){
while (true){
RST(vx, vy); if (dfs(x)) break;
int delta = INF;
REP_2(i, j, n, n) if(vx[i] && !vy[j])
checkMin(delta, w(i, j));
REP(i, n){
if (vx[i]) lx[i] -= delta;
if (vy[i]) ly[i] += delta;
}
}
}
}
void print(){
int res = 0; REP_2(i, j, n, n) res += W[i][j];
REP(i, n) res -= W[p[i]][i];
OT(res);
}
int main(){
init(); KM();
print();
}
const int N = 150;
int W[N][N], lx[N], ly[N], p[N], slack[N];
bool vx[N], vy[N];
int n;
void init(){
RD(n); REP_2(i, j, n, n) RD(W[i][j]);
}
#define w(x, y) (lx[x] + ly[y] - W[x][y])
bool dfs(int x){
vx[x] = true; REP(y, n) if (!vy[y]){
if (!w(x, y)){
vy[y] = true; if(p[y]==-1||dfs(p[y])){
p[y] = x;
return true;
}
}
else {
checkMin(slack[y], w(x, y));
}
}
return false;
}
void KM(){
FLC(p, -1); RST(lx, ly);
REP_2(i, j, n, n) checkMax(lx[i], W[i][j]);
REP(x, n){
FLC(slack, 0x7f); while (true){
RST(vx, vy); if (dfs(x)) break;
int delta = INF;
REP(i, n) if (!vy[i]) checkMin(delta, slack[i]);
REP(i, n){
if (vx[i]) lx[i] -= delta;
if (vy[i]) ly[i] += delta; else slack[i] -= delta;
}
}
}
}
void print(){
int res = 0; REP_2(i, j, n, n) res += W[i][j];
REP(i, n) res -= W[p[i]][i];
OT(res);
}
int main(){
init(); KM();
print();
}
const int N = 150;
int W[N][N], lx[N], ly[N], p[N], delta;
bool vx[N], vy[N];
int n;
void init(){
RD(n); REP_2(i, j, n, n) RD(W[i][j]);
}
#define w(x, y) (lx[x] + ly[y] - W[x][y])
bool dfs(int x){
vx[x] = true; REP(y, n) if (!vy[y]){
if (!w(x, y)){
vy[y] = true; if(p[y]==-1||dfs(p[y])){
p[y] = x;
return true;
}
}
else {
checkMin(delta, w(x, y));
}
}
return false;
}
void KM(){
FLC(p, -1); RST(lx, ly);
REP_2(i, j, n, n) checkMax(lx[i], W[i][j]);
REP(x, n){
while (true){
RST(vx, vy); delta = INF; if (dfs(x)) break;
REP(i, n){
if (vx[i]) lx[i] -= delta;
if (vy[i]) ly[i] += delta;
}
}
}
}
void print(){
int res = 0; REP_2(i, j, n, n) res += W[i][j];
REP(i, n) res -= W[p[i]][i];
OT(res);
}
int main(){
init(); KM();
print();
}
————–
const int INF = 0x3f3f3f3f;
const int N = 302;
int C[N][N], W[N][N];
int Q[512], d[N], p[N], head, tail; bool inQ[N];
int n, s, t, tot, cost;
void init(){
RD(n), s = 0, t = 2 * n + 1, tot = 0;
int w; REP_1(i, n){
C[s][i] = C[i+n][t] = 1;
REP_1(j, n){
C[i][j+n] = 1, tot += _RD(w);
W[i][j+n] = -w, W[j+n][i] = w;
}
}
}
bool spfa(){
RST(inQ); FLC(d, 0x3f), d[Q[head = 0] = s] = 0, tail = 1;
while (head < tail){
int u = Q[head++ & 511]; inQ[u] = false;
FOR_1(v, 1, t){
if (C[u][v] && d[v] > d[u] + W[u][v]){
d[v] = d[u] + W[u][v], p[v] = u;
if (!inQ[v]) Q[tail++ & 511] = v, inQ[v] = true;
}
}
}
return d[t] != INF;
}
void addPath(){
int u, v = t; do{
u = p[v], --C[u][v], ++C[v][u],
cost += W[u][v], v = u;
}while(u != s);
}
void solve(){
cost = 0;
while (spfa()) addPath();
}
int main(){
init(); solve();
OT(tot + cost);
}
Further discussion :
KM-1（ O(n4) 实现。。
KM-2 (.. 标准 O(n3) 实现。。引入 懒标记(slack label) 思想。。。。参见 dd 这篇 。。 :
“… . 维护右边的点 j 的所有不在导出子图的边对应的 lx[i]+ly[j]-w[i][j] 的最小值……”
KM-3（。。自己 yy 的。。dfs 的过程中动态更新 slack。。。O(n3)。。。
—- UPD —-
.. KM-4 .. ( 非递归实现。。。。庶民写法。。。。。。
.. KM-5 .. ( 非递归实现。。。。TC 高端狗写法。。。。。
.. Mincost-Flow-2… （费用流连续增光路算法的 Dijkstra 实现。。。不过在这题里是错的。。因为取负值以后产生了负权环。。。不知道还能不能抢救。。（？
。。注意 KM-3 每次更新可能达不到下界。！！。（。。复杂度不能保证 O(n3) ？。。。
External link :
http://acm.timus.ru/problem.aspx?space=1&num=1076
http://hi.baidu.com/fqq11679/blog/item/9c5c22a69c647392d14358bc.html
http://www.cppblog.com/MatoNo1/archive/2011/07/23/151724.html
