1048:2012-12-28 防卫
- 时间限制:
- 10000ms
- 内存限制:
- 256000kB
- 描述
-
小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏，叫Minecraft。
Tech国和Mana国即将要开战了，小敏带领Tech国修建了许多的据点，据点之间有一些仅允许单向通行的道路。
小敏正在自信满满地准备迎接Mana国的挑战的时候，小燕无意间在远处发现了一大堆Creeper……
这个消息瞬间击倒了小敏。无奈之下，小敏只能在据点上修建一些大炮，保护自己开战的前线不被Creeper给摧毁。也就是说，要保证所有的Creeper在到达前线阵地之前，就已经被大炮给毙了。
不过在不同的据点上修建大炮的费用不一样，小敏希望费用最小。
没有出去道路的据点是前线阵地，Creeper只能从远处进入没有进来道路的据点，并且通过道路进入其他的据点。
- 输入
- 第一行两个整数n和m。
接下来的一行有n个整数，分别代表每个据点修建大炮的费用。
接下来的m行，每行两个整数x和y，分别代表有一条道路从x连到y。 - 输出
- 一行一个整数，表示最小满足条件的费用。
- 样例输入
-
4 41 1 1 11 31 42 32 4
- 样例输出
-
2
- 提示
- 对于100%的数据，n<=1000,m<=6000
「Solution」
最大流+拆点
「代码」
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define maxn 20000
#define INF 1 << 30
using namespace std;
struct E
{
int from, to, tab, next;
}edge[maxn];
int dist[maxn], head[maxn], d[maxn], in[maxn], out[maxn], ans, s, t, tot, m, n;
void add_edge(int u, int v, int f)
{
tot++;
edge[tot].from = u, edge[tot].to = v, edge[tot].tab = f, edge[tot].next = head[u], head[u] = tot;
tot++;
edge[tot].from = v, edge[tot].to = u, edge[tot].tab = 0, edge[tot].next = head[v], head[v] = tot;
}
int dfs(int x, int low)
{
int a;
if (x == t) return low;
for (int i = head[x]; i != -1; i = edge[i].next)
if (dist[edge[i].to] == dist[x] + 1 && edge[i].tab > 0 && (a = dfs(edge[i].to, min(low, edge[i].tab))))
{
edge[i].tab -= a, edge[i^1].tab += a;
return a;
}
return 0;
}
int bfs()
{
int l, r, k;
memset(dist, 0xff, sizeof(dist));
dist[s] = 0;
d[0] = 0, d[1] = s;
l = 0, r = 1;
while (l < r)
{
k = d[++l];
for (int i = head[k]; i != -1; i = edge[i].next)
if (edge[i].tab > 0 && dist[edge[i].to] < 0) dist[edge[i].to] = dist[k] + 1, d[++r] = edge[i].to;
}
if (dist[t] > 0) return 1; else return 0;
}
void dinic()
{
ans = 0;
while (bfs()) ans += dfs(s, INF);
}
int main()
{
int x, y, f;
tot = -1;
memset(head,0xff,sizeof(head));
scanf("%d%d", &n, &m);
s = 2 * n + 1, t = 2 * n + 2;
for (int i = 1; i <= n; i++)
{
scanf("%d", &f);
add_edge(i, i+n, f);
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &x, &y);
in[y]++, out[x]++;
add_edge(x+n, y, INF);
}
for (int i = 1; i <= n; i++)
{
if (in[i] == 0) add_edge(s, i, INF);
if (out[i] == 0) add_edge(i+n, t, INF);
}
dinic();
printf("%d\n", ans);
return 0;
}