Description

小白在图论课上学到了一个新的概念--最小割, 下课后小白在笔记本上写下了如下这段话:

对于一个图, 某个对图中结点的划分将图中所有结点分成两个部分, 如果结点 \(s, t\) 不在同一个部分中, 则称这个划分是关于 \(s, t\) 的割. 对于带权图来说, 将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量, 而 \(s, t\) 的最小割 指的是在关于 \(s, t\) 的割中容量最小的割.

现给定一张无向图, 小白有若干个形如 “图中有多少对点它们的最小割的容量不超过 x 呢”“的疑问, 小蓝虽然很想回答这些问题, 但小蓝最近忙着挖木块, 于是作为仍然是小蓝的好友, 你又有任务了.

Input

输入文件第一行有且只有一个正整数 \(T\), 表示测试数据的组数.

对于每组测试数据, 第一行包含两个整数 \(n, m\), 表示图的点数和边数; 下面 \(m\) 行, 每行 \(3\) 个正整数 \(u, v, c (1 \leq u, v \leq n, 0 \leq c \leq 10^6)\), 表示有一条权为 \(c\) 的无向边 \((u, v)\);

接下来一行, 包含一个整数 \(q\), 表示询问的个数下面 \(q\) 行, 每行一个整数 \(x\), 其含义同题目描述.

Output

对于每组测试数据, 输出应包括 \(q\) 行, 第 \(i\) 行表示第 \(i\) 个问题的答案.

对于点对 \((p, q)\) 和 \((q, p)\), 只统计一次 (见样例). 两组测试数据之间用空行隔开.

Sample Input

1
5 0
1
0

Sample Output

10

Data Range

对于 100% 的数据, 满足:\(T \leq 10, n \leq 150, m \leq 3000, q \leq 30, x \leq 2^{31}-1\).

图中两个点之间可能有多条边.

Explanation

fhq 神犇题解:

首先, 注意这样一个事实: 如果 (X, Y) 是某个 s1-t1 最小割, (Z, W) 是某个 s2-t2 最小割, 那么 \(X \cap Z, X \cap W, Y \cap Z, Y \cap W\) 这四项不可能均非空. 也就是说, 最小割不可能相互跨立.

这个蕴含了, 最多一共有 \(n - 1\) 个不同的 \(s - t\) 最小割. 只需把这些割找出来即可.

寻找的方法: 首先, 在 \(V\) 中任意找两个点 \(a, b\), 求最大流, 把 \(V\) 划分为割 \(X-Y\), 之后对 \(X, Y\) 分别递归地进行划分. 这样就能得到 \(n - 1\) 个割了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 160, maxm = 100100;
const int infinit = 0x3f3f3f3f;

class Dinic
{
public:
    struct edge
    {
        int u, v, flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    bool mark[maxn];
    void add_edge(int u, int v, int flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        q->u = v; q->v = u; q->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        level[s] = 1;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] == 0)
            return false;
        return true;
    }
    int find(int p, int mn)
    {
        if (p == t)
            return mn;
        int sum = 0, tmp;
        for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = find(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                    sum += tmp;
                }
            }
        if (sum < mn)
            level[p] = 0;
        return sum;
    }
    int eval(void)
    {
        int sum = 0;
        while (make_level()) {
            int tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
    void decl_dfs(int p)
    {
        mark[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (ep->flow && !mark[ep->v])
                decl_dfs(ep->v);
        return ;
    }
    void mark_tree(int p)
    {
        memset(mark, 0, sizeof(mark));
        decl_dfs(p);
        return ;
    }
    void init(int n)
    {
        this->n = n;
        memset(edges, 0, sizeof(edges));
        ecnt = 0;
        return ;
    }
    void revert(void)
    {
        for (int i = 1; i <= ecnt; i++) {
            edge *p = &epool[i],
                 *q = p->rev;
            p->flow = q->flow = (p->flow + q->flow) / 2;
        }
        return ;
    }
} graph;

int T, n, m, Q;
int a[maxn], tmp[maxn];
int stat[maxn][maxn];

void recr_solve(int l, int r)
{
    if (l == r)
        return ;
    graph.revert();
    graph.s = a[l];
    graph.t = a[r];
    // Running and judging connexions
    int cut = graph.eval();
    graph.mark_tree(graph.s);
    // Evaluating result array
    rep(i, 1, n) if (graph.mark[i]) rep(j, 1, n) if (!graph.mark[j])
        stat[i][j] = stat[j][i] = min(stat[i][j], cut);
    // Marking bounds
    int L = l, R = r;
    rep(i, l, r)
        if (graph.mark[a[i]]) tmp[L++] = a[i];
        else tmp[R--] = a[i];
    rep(i, l, r)
        a[i] = tmp[i];
    // Recursing.
    recr_solve(l, L - 1);
    recr_solve(R + 1, r);
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d%d", &n, &m);
        graph.init(n);
        // Adding edges
        for (int i = 1, u, v, f; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &f);
            graph.add_edge(u, v, f);
        }
        // Cleaning result array
        rep(i, 1, n) rep(j, 1, n)
            stat[i][j] = infinit;
        rep(i, 1, n)
            a[i] = i;
        // Recursively, solving
        recr_solve(1, n);
        scanf("%d", &Q);
        for (int qdx = 1, x; qdx <= Q; qdx++) {
            scanf("%d", &x);
            int res = 0;
            for (int i = 1; i <= n; i++)
                for (int j = i + 1; j <= n; j++)
                    if (stat[i][j] <= x)
                        res += 1;
            printf("%d\n", res);
        }
        printf("\n");
    }
    return 0;
}