Tsinsen A1220. 复杂的大门(陈许旻)

问题描述

  你去找某bm玩,到了门口才发现要打开他家的大门不是一件容易的事……
他家的大门外有n个站台,用1到n的正整数编号。你需要对每个站台访问一定次数以后大门才能开启。站台之间有m个单向的传送门,通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门,你就需要乘坐公共汽车,并花费1单位的钱。值得庆幸的是,任意两个站台之间都有公共汽车直达。
现在给你每个站台必须访问的次数Fi,对于站台i,你必须恰好访问Fi次(不能超过)。
我们用u、v、w三个参数描述一个传送门,表示从站台u到站台v有一个最多可以使用w次的传送门(不一定要使用w次)。值得注意的是,对于任意一对传送门(u1,v1)和(u2,v2),如果有u1<u2,则有v1≤v2;如果有v1<v2,则有u1≤u2;且u1=u2和v1=v2不同时成立。
你可以从任意的站台开始,从任意的站台结束。出发去开始的站台需要花费1单位的钱。你需要求出打开大门最少需要花费多少单位的钱。

输入格式

  第一行包含两个正整数n、m,意义见题目描述。
第二行包含n个正整数,第i个数表示Fi
接下来有m行,每行有三个正整数u、v、w,表示从u到v有一个可以使用w次的传送门。

输出格式

  输出一行一个整数,表示打开大门最少花费的钱数。

样例输入

4 3
5 5 5 5
1 2 1
3 2 1
3 4 1

样例输出

17

数据规模及约定

  有20%的数据满足n≤10,m≤50;对于所有的w、Fi,满足1≤w,Fi≤10。有50%的数据满足n≤1000,m≤10000。100%的数据满足1≤n≤10000,1≤m≤100000;对于所有的u、v,满足1≤u,v≤n,u≠v;对于所有的w、Fi,满足1≤w,Fi≤50000。
以上的每类数据中都存在50%的数据满足对于所有的w、Fi,有w=Fi=1。
时限1s

题解

题目就是说给你一些点,每个点必须且只经过\(F_i\)次,瞬移(从任意点到任意点)一次代价1,走边不花费代价,但是一条边只能走\(w_i\)次,问走完这\(\sum F_i\)次点后最小代价多少。

大概就是最小路径覆盖了,改一下普通建图方式即可过。

代码

#include <cstdio>
const int maxn = 10005;
const int maxnode = maxn * 2 + 100;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int n, m;
int F[maxn];
struct edge_type {
    int to, next, r;
} edge[300005];
int S, T, cnte = 1, h[maxnode];
int Q[maxn * 2 + 100];
void ins(int u, int v, int f) {
    ++cnte;
    edge[cnte].to = v;
    edge[cnte].r = f;
    edge[cnte].next = h[u];
    h[u] = cnte;
    ++cnte;
    edge[cnte].to = u;
    edge[cnte].r = 0;
    edge[cnte].next = h[v];
    h[v] = cnte;
}
int tail, head, d[maxnode], cur[maxnode];
bool bfs() {
    tail = head = 0;
    for (int i = S; i <= T; ++i) d[i] = -1;
    Q[tail++] = S;
    d[S] = 0;
    int now;
    while (head < tail) {
        now = Q[head++];
        for (int i = h[now]; i; i = edge[i].next) {
            if (d[edge[i].to] == -1 && edge[i].r) {
                d[edge[i].to] = d[now] + 1;
                Q[tail++] = edge[i].to;
            }
        }
    }
    return d[T] != -1;
}
int min(int a, int b) {
    return a < b ? a : b;
}
int dfs(int now, int a) {
    if (T == now || a == 0) return a;
    int ret = 0, f;
    for (int &i = cur[now]; i; i = edge[i].next) {
        if (d[edge[i].to] != d[now]+1) continue;
        if (f = dfs(edge[i].to, min(a, edge[i].r))) {
            a -= f;
            ret += f;
            edge[i].r -= f;
            edge[i^1].r += f;
            if (a == 0) break;
        }
    }
    if (ret == 0) d[now] = -1;
    return ret;
}
const int INF = 1<<30;
int Dinic() {
    int ret = 0;
    while (bfs()) {
        for (int i = S; i <= T; ++i)
            cur[i] = h[i];
        ret += dfs(S, INF);
    }
    return ret;
}
int main() {
    n = getint(); m = getint();
    S = 0; T = maxn + maxn;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        F[i] = getint();
        ans += F[i];
        ins(S, i, F[i]);
        ins(i + maxn, T, F[i]);
    }
    int x, y, z;
    for (int i = 1; i <= m; ++i) {
        x = getint();
        y = getint();
        z = getint();
        ins(x, y + maxn, z);
    }
    int tmp = Dinic();
    printf("%d", ans - tmp);
}

 

Show Comments