题目描述
小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： ”对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。
对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割“
现给定一张无向图，小白有若干个形如”图中有多少对点它们的最小割的容量不超过x呢“的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为仍然是小蓝的好友，你又有任务了。
输入格式
输入文件第一行有且只有一个正整数T，表示测试数据的组数。 对于每组测试数据， 第一行包含两个整数n,m，表示图的点数和边数。 下面m行，每行3个正整数u,v,c(1<=u,v<=n,0<=c<=106)，表示有一条权为c的无向边(u,v) 接下来一行，包含一个整数q，表示询问的个数 下面q行，每行一个整数x，其含义同题目描述。
输出格式
对于每组测试数据，输出应包括q行，第i行表示第i个问题的答案。对于点对(p,q)和(q,p)，只统计一次（见样例）。两组测试数据之间用空行隔开。
输入输出样例
输入 #1复制
1
5 0
1
0
输出 #1复制
10
说明/提示
【数据范围】
对于100%的数据 T<=10,n<=150,m<=3000,q<=30，x在32位有符号整数类型范围内。
图中两个点之间可能有多条边
先求一下最小割树，把任意两点间的距离加入到vector当中，最后upper_bound找一下即可。
但是要注意，如果不能到达，应该返回0，而不是INF。
还有输出空行
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=210,M=1e5+10;
int n,m,q,T;
struct maxflow{
int head[N],nex[M],to[M],w[M],h[N],tot=1,s,t; queue<int> q;
inline void ade(int a,int b,int c){
to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){ade(a,b,c); ade(b,a,0);}
inline int bfs(){
q.push(s); memset(h,0,sizeof h); h[s]=1;
while(q.size()){
int u=q.front(); q.pop();
for(int i=head[u];i;i=nex[i]){
if(w[i]&&!h[to[i]]){
h[to[i]]=h[u]+1; q.push(to[i]);
}
}
}
return h[t];
}
int dfs(int x,int f){
if(x==t) return f; int fl=0;
for(int i=head[x];i&&f;i=nex[i]){
if(w[i]&&h[to[i]]==h[x]+1){
int mi=dfs(to[i],min(w[i],f));
w[i]-=mi,w[i^1]+=mi,fl+=mi,f-=mi;
}
}
if(!fl) h[x]=-1;
return fl;
}
inline void init(){
for(int i=2;i<=tot;i+=2) w[i]+=w[i^1],w[i^1]=0;
}
inline int dinic(){
int res=0; init();
while(bfs()) res+=dfs(s,inf);
return res;
}
}d;
struct min_cut_tree{
int head[N],nex[M],to[M],w[M],tot=0;
inline void ade(int a,int b,int c){
to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){ade(a,b,c); ade(b,a,0);}
int a[N],b[N],c[N];
void build(int l,int r){
if(l==r) return ;
d.s=a[l],d.t=a[l+1]; int flow=d.dinic();
add(a[l],a[l+1],flow);
int cnt1=0,cnt2=0;
for(int i=l;i<=r;i++){
if(d.h[a[i]]) b[++cnt1]=a[i];
else c[++cnt2]=a[i];
}
for(int i=l;i<=l+cnt1-1;i++) a[i]=b[i-l+1];
for(int i=l+cnt1;i<=r;i++) a[i]=c[i-cnt1-l+1];
build(l,l+cnt1-1); build(l+cnt1,r);
}
int h[N],f[N][10],mi[N][10],lg[N];
void dfs(int x,int fa){
h[x]=h[fa]+1;
for(int i=1;(1<<i)<=h[x];i++){
f[x][i]=f[f[x][i-1]][i-1];
mi[x][i]=min(mi[x][i-1],mi[f[x][i-1]][i-1]);
}
for(int i=head[x];i;i=nex[i]){
if(to[i]==fa) continue;
f[to[i]][0]=x; mi[to[i]][0]=w[i];
dfs(to[i],x);
}
}
void solve(){
for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
memset(head,0,sizeof head); tot=0;
for(int i=1;i<=n;i++) a[i]=i;
build(1,n); dfs(1,0);
}
inline int ask(int x,int y){
int res=inf;
if(h[x]<h[y]) swap(x,y);
while(h[x]>h[y]){
res=min(res,mi[x][lg[h[x]-h[y]]-1]);
x=f[x][lg[h[x]-h[y]]-1];
}
if(x==y) return res;
for(int i=lg[h[x]]-1;i>=0;i--){
if(f[x][i]!=f[y][i]){
res=min(res,mi[x][i]); res=min(res,mi[y][i]);
x=f[x][i],y=f[y][i];
}
}
res=min(res,mi[x][0]); res=min(res,mi[y][0]);
if(res==inf) return 0;
return res;
}
}mct;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin>>T;
while(T--){
cin>>n>>m; d.tot=1; memset(d.head,0,sizeof d.head);
for(int i=1,a,b,c;i<=m;i++) cin>>a>>b>>c,d.add(a,b,c),d.add(b,a,c);
vector<int> v; mct.solve();
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++) v.push_back(mct.ask(i,j));
sort(v.begin(),v.end());
cin>>q;
while(q--){
int x; cin>>x;
cout<<upper_bound(v.begin(),v.end(),x)-v.begin()<<'\n';
}
cout<<'\n';
}
return 0;
}
京公网安备 11010502036488号