[CQOI2016]不同的最小割

2018-04-26

lolifamily

无向图任意点对最大流的模板题，暴力把所有元素用 bitset 排重即可。

Problem

题目描述

学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 $𝑠, 𝑡$ 不在同一个部分中，则称这个划分是关于 $𝑠, 𝑡$ 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 $𝑠, 𝑡$ 的最小割指的是在关于 $𝑠, 𝑡$ 的割中容量最小的割。

而对冲刺 NOI 竞赛的选手而言，求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽，考虑有 $𝑁$ 个点的无向连通图中所有点对的最小割的容量，共能得到 $𝑁 (𝑁 - 1) 2$ 个数值。这些数值中互不相同的有多少个呢？这似乎是个有趣的问题。

输入格式

第一行包含两个数 $𝑁, 𝑀$ ，表示点数和边数。

接下来 $𝑀$ 行，每行三个数 $𝑢, 𝑣, 𝑤$ ，表示点 $𝑢$ 和点 $𝑣$ （从 $1$ 开始标号）之间有一条权值是 $𝑤$ 的边。

输出格式

第一行为一个整数，表示不同的最小割容量的个数。

输入

输出

1
3

说明 / 提示

$1 \leq 𝑁 \leq 850$ ， $1 \leq 𝑀 \leq 8500$ ， $1 \leq 𝑤 \leq 100000$ 。

Code

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