记录编号 |
101668 |
评测结果 |
AAAAAAAAAA |
题目名称 |
搬运工 |
最终得分 |
100 |
用户昵称 |
OI永别 |
是否通过 |
通过 |
代码语言 |
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;
}