admin 管理员组

文章数量: 1184232

防卫

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;
}



本文标签： 防卫

版权声明：本文标题：防卫 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1688432432a219278.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。