题意: 给出一张 n 个点 m 条边的无向图, 边权均为 1, 敌人在 n 点准备走最短路在攻击己方位置 1 点, 现在要在一些边上设置一些路障, 给出每条边设置路障的代价, 要求用最少的代价设置路障使得敌人必然遇到路障.
这份代码了用到了当前弧优化, 尽管我不是很懂...
但素不用的话会超时!
- #include<stdio.h>
- #include<string.h>
- #include<queue>
- using namespace std;
- struct node {
- int from;
- int to;
- int w;
- int next;
- }e[160000];
- int cur[1500];
- int head[1500];
- int divv[1500];
- int cont, ss, tt;
- void add(int from, int to, int w) {
- e[cont].from = from;
- e[cont].w = w;
- e[cont].to = to;
- e[cont].next = head[from];
- head[from] = cont++;
- }
- int n, m;
- int makedivv() {
- memset(divv, 0, sizeof(divv));
- divv[ss] = 1;
- queue<int>s;
- s.push(ss);
- while (!s.empty()) {
- int u = s.front();
- if (u == tt)return 1;
- s.pop();
- for (int i = head[u]; i != -1; i = e[i].next) {
- int w = e[i].w;
- int v = e[i].to;
- if (divv[v] == 0 && w) {
- divv[v] = divv[u] + 1;
- s.push(v);
- }
- }
- }
- return 0;
- }
- int Dfs(int u, int maxflow, int tt) {
- if (u == tt)return maxflow;
- int ret = 0;
- // 当前弧优化
- for (int &i = cur[u]; i != -1; i = e[i].next) {
- int v = e[i].to;
- int w = e[i].w;
- if (divv[v] == divv[u] + 1 && w) {
- int f = Dfs(v, min(maxflow - ret, w), tt);
- e[i].w -= f;
- e[i ^ 1].w += f;
- ret += f;
- if (ret == maxflow)return ret;
- }
- }
- return ret;
- }
- void Dinic() {
- long long int ans = 0;
- while (makedivv() == 1) {
- memcpy(cur, head, sizeof(head));
- ans += Dfs(ss, 0x3f3f3f3f, tt);
- }
- printf("%lld\n", ans % 100000);
- }
- int main() {
- int t;
- scanf("%d", &t);
- while (t--) {
- scanf("%d%d", &n, &m);
- scanf("%d%d", &ss, &tt);
- cont = 0;
- memset(head, -1, sizeof(head));
- for (int i = 0; i < m; i++) {
- int x, y, z;
- scanf("%d%d%d", &x, &y, &z);
- add(x, y, z); add(y, x, 0);
- }
- Dinic();
- }
- }
来源: http://www.bubuko.com/infodetail-2580316.html