URAL 1076. Trash

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