2014-07-28

UVa 11765 - Component Placement

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for Sample Input
6. Solution

Problem

In circuit design, component placement is an important step in the design automation. Inferior placements may affect the performance and manufacturing cost.

You are given a PCB (Printed Circuit Board). It’s a large green board. You can place components on either side of the PCB. However, cost of placing a component on both sides are not the same. You are given N components. For each component ci, cost of placing it on the top layer is Xi and on the bottom layer is Yi.

These components may interact with each other. If both the components are on the same side of the PCB, the interconnection cost is negligible. But, if they are on different sides, their interconnection is costly. For each such interconnection j, the cost will be Zj.

Finally, some design issues restricts some components to be on the top side or bottom side. Now, find the minimum cost to place the components.

Input

First line contains a positive integer T (T<= 50) that denotes the number of test cases.

Each test case starts with 2 integers N (1 <= N <= 200) and M (0 <= M <= 100000, M <= N * (N-1) / 2), the number of components and number of interconnections. This will be followed by N integers in a line, each between 1 and 10000000 (inclusive), where i-th of it describes the cost of placing the component on the top layer. The next line contains N more integers, each between 1 and 10000000 (inclusive), where i-th of it denotes the cost of placing it on the bottom layer. The next line contains N more integers, each will be either 0, -1 or +1, where

-1 means i-th component can only be placed on the bottom
+1 means i-th component can only be placed on the top
0 means the component can be placed on either side

Then there will be M lines, each containing three integers, p, q, and r (1 <= p, q <= N, 1 <= r <= 10000000), denoting that, p and q-th component has to be interconnected and if they are on different layers, the cost of interconnection will be r. There will be at most one interconnection between any pair or components.

Output

For each test case, output the minimum cost to place the components.

Sample Input

5
4 0
5 6 7 8
8 7 6 5
0 0 0 0
4 2
5 6 7 8
8 7 6 5
0 0 0 0
1 3 10
2 4 10
4 3
5 6 7 8
8 7 6 5
0 0 0 0
1 3 10
2 4 10
2 3 1
4 3
5 6 7 8
30 31 32 33
0 0 0 0
1 3 10
2 4 10
2 3 1
4 3
5 6 7 8
8 7 6 5
-1 0 0 1
1 2 10
3 4 10
2 3 1

Output for Sample Input

Solution

題目描述：

有一些元件，設置在電路板上面時，要不放上面或者是放下面，放置的成本各有不同，假如兩個元件之間必須相連，則當他們放置在不同側的時候，會有額外的花費，如果放在同側則無需考慮。

求放置的最小成本。

題目解法：

利用最大流 = 最小割的方式，將不同側的成本反應在最小割上面。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
struct Node {
    int x, y, v;// x->y, v
    int next;
} edge[100005];
int e, head[505], prev[505], record[505];
int level[505], visited[505];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].v = v;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].v = 0;
    edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
    memset(level, 0, sizeof(level));
    queue<int> Q;
    Q.push(s), level[s] = 1;
    while(!Q.empty()) {
        int tn = Q.front();
        Q.pop();
        for(int i = head[tn]; i != -1; i = edge[i].next) {
            int y = edge[i].y;
            if(edge[i].v > 0 && level[y] == 0) {
                level[y] = level[tn] + 1;
                Q.push(y);
            }
        }
    }
    return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
    int ret = 0;
    stack<int> stk;
    memset(visited, 0, sizeof(visited));
    stk.push(s);
    while(!stk.empty()) {
        int now = stk.top();
        if(now != t) {
            for(int i = head[now]; i != -1; i = edge[i].next) {
                int y = edge[i].y;
                if(visited[y] || level[y] != level[now] + 1)
                    continue;
                if(edge[i].v > 0) {
                    stk.push(y), prev[y] = now, record[y] = i;
                    break;
                }
            }
            if(stk.top() == now)
                stk.pop(), visited[now] = 1;
        } else {
            int flow = 1e+9, bottleneck;
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                flow = min(flow, edge[ri].v);
            }
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                edge[ri].v -= flow;
                edge[ri^1].v += flow;
                if(edge[ri].v == 0)
                    bottleneck = prev[i];
            }
            while(!stk.empty() && stk.top() != bottleneck)
                stk.pop();
            ret += flow;
        }
    }
    return ret;
}
int maxflowDinic(int s, int t) {
    int flow = 0;
    while(buildLevelGraph(s, t))
        flow += constructBlockingFlow(s, t);
    return flow;
}
int main() {
    int n, m, testcase;
    int U[1024], D[1024], kind, x, y, v;
    scanf("%d", &testcase);
    while(testcase--) {
        e = 0;
        memset(head, -1, sizeof(head));
        
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
        	scanf("%d", &U[i]);
        for(int i = 0; i < n; i++)
        	scanf("%d", &D[i]);
    	
    	int source = n + 1, sink = source + 1;
    	const int INF = 0x3f3f3f3f;
        for(int i = 0; i < n; i++) {
        	scanf("%d", &kind);
        	if(kind == 0) {
        		addEdge(source, i, U[i]);
        		addEdge(i, sink, D[i]);
        	} else if(kind == 1) {
        		addEdge(source, i, U[i]);
        		addEdge(i, sink, INF);
        	} else {
        		addEdge(source, i, INF);
        		addEdge(i, sink, D[i]);
        	}
        }
        for(int i = 0; i < m; i++) {
        	scanf("%d %d %d", &x, &y, &v);
        	x--, y--;
        	addEdge(x, y, v);
        	addEdge(y, x, v);
        }
        printf("%d\n", maxflowDinic(source, sink));
    }
    return 0;
}

Morris' Blog