2229: [Zjoi2011]最小割
题目：传送门
题解：
一道非常好的题目啊！！！
蒟蒻的想法：暴力枚举点对跑最小割记录...绝对爆炸啊....
开始怀疑是不是题目骗人...难道根本不用网络流？？？一看路牌....分治最小割？最小割树？
然后开始各种%论文...
简单来说吧，根据各种本蒟蒻不会证明的理论，那么：所有最小割都不是完全独立的，总共有n-1种（也就是树上的n-1条边）最小割 恰好和树的定义一样啊！
那么用一个solve递归函数来解决，一开始任意找两个点作为st和ed来最小割，然后分治，在分开的两个集合中继续递归，用数组记录答案
以上都是根据边所进行的离线操作，然后输入Q个询问，直接在线输出答案就ok
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int inf=;
struct node
{
int x,y,c,next,other;
}a[];int len,last[];
int st,ed,n,m,T,ans;
void ins(int x,int y,int c)
{
int k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=c;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int list[],h[],head,tail;
bool bt_h()
{
memset(h,,sizeof(h));h[st]=;
list[]=st;head=;tail=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]== && a[k].c)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed])return true;
return false;
}
int find_flow(int x,int flow)
{
if(x==ed)return flow;
int s=,t;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]+ && a[k].c && s<flow)
{
s+=t=find_flow(y,min(a[k].c,flow-s));
a[k].c-=t;a[a[k].other].c+=t;
}
}
if(s==)h[x]=;
return s;
}
int d[],num[],sta[],anss[][];
void re_num(int x)
{
num[x]=;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k].c && !num[y])
re_num(y);
}
}
void solve(int l,int r)
{
if(l==r)return ;
for(int i=;i<=len;i+=)a[i].c=a[i+].c=(a[i].c+a[i+].c)>>;//将边权重置
st=d[l];ed=d[r];ans=;
while(bt_h())ans+=find_flow(st,inf);
memset(num,,sizeof(num));
re_num(st);
for(int i=;i<=n;i++)
if(num[i])
for(int j=;j<=n;j++)
if(!num[j])
anss[i][j]=anss[j][i]=min(anss[i][j],ans);
int L=l,R=r;
for(int i=l;i<=r;i++)
{
if(num[d[i]])sta[L++]=d[i];
else sta[R--]=d[i];
}
for(int i=l;i<=r;i++)d[i]=sta[i];
solve(l,L-);solve(R+,r);//分治，递归
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
len=;memset(last,,sizeof(last));int x,y,c;
for(int i=;i<=m;i++)scanf("%d%d%d",&x,&y,&c),ins(x,y,c);
for(int i=;i<=n;i++)d[i]=i;memset(anss,,sizeof(anss));
solve(,n);
int Q;scanf("%d",&Q);
while(Q--)
{
scanf("%d",&x);int cnt=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
if(anss[i][j]<=x)
cnt++;
printf("%d\n",cnt);
}
printf("\n");
}
return ;
}