[ZJOI2011]最小割

2018-04-26

lolifamily

无向图任意点对最大流的模板题，把所有元素放进 num 数组里排序 + 二分即可。

Problem

题目描述

小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： “对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 $𝑠, 𝑡$ 不在同一个部分中，则称这个划分是关于 $𝑠, 𝑡$ 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 s,t 的最小割指的是在关于 $𝑠, 𝑡$ 的割中容量最小的割”

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

输入格式

输入文件第一行有且只有一个正整数 $𝑇$ ，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $𝑛$ , $𝑚$ ，表示图的点数和边数。

下面 $𝑚$ 行，每行 $3$ 个正整数 $𝑢$ , $𝑣$ , $𝑐$ ，表示有一条权为 $𝑐$ 的无向边 $(𝑢, 𝑣)$

接下来一行，包含一个整数 $𝑞$ ，表示询问的个数

下面 $𝑞$ 行，每行一个整数 $𝑥$ ，其含义同题目描述。

输出格式

对于每组测试数据，输出应包括 $𝑞$ 行，第 $𝑖$ 行表示第 $𝑖$ 个问题的答案。对于点对 $(𝑝, 𝑞)$ 和 $(𝑞, 𝑝)$ ，只统计一次（见样例）。

两组测试数据之间用空行隔开。

输入

输出

1
10

说明/提示

对于 $100 %$ 的数据， $1 \leq 𝑇 \leq 10$ ， $1 \leq 𝑛 \leq 150$ ， $0 \leq 𝑚 \leq 3000$ ， $0 \leq 𝑥 \leq 231 - 1$ ， $0 \leq 𝑞 \leq 30$ 。

Code

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define inf 0x3FFFFFFF
6
using namespace std;
7
struct Node
8
{
9
  int to,next,v;
10
}e[6005],mp[6005];
11
int s,t,n,m,h[155],f[155][155],d[155],gap[155],fa[155],num[22505],cnt=1;
12
bool vis[155];
13
inline void Addedge(int x,int y,int v)
14
{
15
  mp[++cnt]=(Node){y,h[x],v};h[x]=cnt;return;
16
}
17
inline int dfs(int x,int maxf)
18
{
19
  int i,y,ret=0,delta;
20
  if(x==t)return maxf;
21
  for(i=h[x];i;i=e[i].next)
22
  {
23
    y=e[i].to;
24
    if(e[i].v&&d[x]==d[y]+1)
25
    {
26
      delta=dfs(y,min(maxf,e[i].v));
27
      e[i].v-=delta;
28
      e[i^1].v+=delta;
29
      ret+=delta;
30
      maxf-=delta;
31
      if(!maxf||d[x]==n)return ret;
32
    }
33
  }
34
  if(!(--gap[d[x]]))d[s]=n;
35
  ++gap[++d[x]];
36
  return ret;
37
}
38
inline void dfs(int x)
39
{
40
  int i,y;
41
  vis[x]=true;
42
  for(i=h[x];i;i=e[i].next)
43
  {
44
    y=e[i].to;
45
    if(e[i].v&&!vis[y])dfs(y);
46
  }
47
  return;
48
}
49
inline void Gusfield()
50
{
51
  int i,j,ans;
52
  memset(f,0x3F,sizeof(f));
53
  for(i=2;i<=n;++i)fa[i]=1;
54
  for(i=2;i<=n;++i)
55
  {
56
    memcpy(e,mp,sizeof(mp));
57
    memset(gap,0,sizeof(gap));
58
    memset(d,0,sizeof(d));
59
    memset(vis,0,sizeof(vis));
60
    s=fa[i];t=i;ans=0;
61
    gap[0]=n;
62
    while(d[s]<n)ans+=dfs(s,inf);
63
    dfs(s);
64
    for(j=i+1;j<=n;++j)
65
    {
66
      if(!vis[j]&&fa[j]==fa[i])fa[j]=i;
67
    }
68
    for(j=1;j<i;++j)f[i][j]=f[j][i]=min(f[fa[i]][j],ans);
69
  }
70
  return;
71
}
72
int main(void)
73
{
74
  int i,j,q,T,x,y,v;
75
  scanf("%d",&T);
76
  while(T--)
77
  {
78
    memset(h,0,sizeof(h));cnt=1;
79
    scanf("%d%d",&n,&m);
80
    for(i=1;i<=m;++i)
81
    {
82
      scanf("%d%d%d",&x,&y,&v);
83
      Addedge(x,y,v);
84
      Addedge(y,x,v);
85
    }
86
    Gusfield();num[0]=0;
87
    for(i=1;i<=n;++i)
88
    {
89
      for(j=i+1;j<=n;++j)
90
      {
91
        num[++num[0]]=f[i][j];
92
      }
93
    }
94
    sort(num+1,num+num[0]+1);
95
    scanf("%d",&q);
96
    for(i=1;i<=q;++i)
97
    {
98
      scanf("%d",&x);
99
      printf("%d\n",upper_bound(num+1,num+num[0]+1,x)-num-1);
100
    }
101
    putchar('\n');
102
  }
103
  return 0;
104
}