记录编号 101668 评测结果 AAAAAAAAAA
题目名称 搬运工 最终得分 100
用户昵称 GravatarOI永别 是否通过 通过
代码语言 C++ 运行时间 0.008 s
提交时间 2014-05-13 18:45:46 内存使用 1.54 MiB
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 805
#define INC 1000000
#define INF 2147483647
#define M 80005
int n;
struct arr{
	int ff, tt, ww, next;
}c[M];
queue<int> Q;
int d[N];
int r[N];
int tot = 1;
inline void add(int x, int y, int z){
	c[++tot].ff = x;c[tot].tt = y;c[tot].ww = z;c[tot].next = r[x];r[x] = tot;
	c[++tot].ff = y;c[tot].tt = x;c[tot].ww = 0;c[tot].next = r[y];r[y] = tot;
	return ;
}
int st, ed;

bool bfs(){
	memset(d, 0, sizeof(d));
	d[st] = 1;
	while (Q.size()) Q.pop();
	Q.push(st);
	while (Q.size()){
		int x = Q.front();
		Q.pop();
		for (int i = r[x]; i; i = c[i].next){
			int y = c[i].tt;
			if (!d[y] && c[i].ww > 0){
				d[y] = d[x] + 1;
				if (y == ed) return 1;
				Q.push(y);
			}
		}
	}
	return 0;
}

int dinic(int x, int f){
	if (x == ed) return f;
	int temp = f;
	for (int i = r[x]; i; i = c[i].next){
		int y = c[i].tt;
		if (d[y] == d[x] + 1 && c[i].ww > 0 && temp > 0){
			int k = dinic(y, min(temp, c[i].ww));
			if (!k) d[y] = 0;
			c[i].ww -= k;
			c[i ^ 1].ww += k;
			temp -= k;
		}
	}
	return f - temp;
}

int main(){
	freopen("worker.in", "r", stdin);
	freopen("worker.out", "w", stdout);
	scanf("%d",&n);
	st = 0; ed = n + n + 1;
	char ch;
	for (int i = 1; i <= n; i ++){	
		for (int j = 1; j <= n; j ++){
			while (1){
				ch = getchar();
				if (ch == '.' || ch == '*') break;
			}
			if (ch == '*'){
				add(i, n + j, INF);
			}
		}
	}
	int x;
	for (int i = 1; i <= n; i ++){
		scanf("%d", &x);
		add(st, i, x + INC);
	}
	for (int i = 1; i <= n; i ++){
		scanf("%d", &x);
		add(i + n, ed, x + INC);
	}
	int i, maxflow = 0;
	while (bfs()){
		while (i = dinic(st, INF)) maxflow += i;
	}
	printf("%d\n%d\n", maxflow / INC, maxflow % INC);
	return 0;
}