题意简述
第一个题 : 问图中有多少不同的最小割数值
第二个题 : (q) 次询问图中多少对点对之间的最小割小于 (x) 。
Sol
两个都是模板题就放一起了。
求完最小割树直接暴力 (O(n^2)) 弄出所有点对间最小割 , 然后该干嘛干嘛。
最小割树的构建:
(Gemory-Hu; Tree)算法
对于一个 (n) 个节点的图 , 图中所有点对不同的最小割数目最多只有 (n-1) 个 , 可以证明存在一棵树 , 使得两点在这棵树上的最小割即为原图中的最小割 。
考虑3个点两两之间的最小割 (C_{u,v},C_{u,t},C_{v,t}) , 我们已知 (C_{u,t},C_{v,t}) , 假设在(C_{u,v})中 ,不妨假设 (t) 被分在了与 (v) 在一起的割集 。由于在一个割中一个点一定被分在源点或者汇点的一侧割集 , 那么可以推出 (C_{u,v}leq C_{u,t}) , 如果不是那么显然直接割掉 (u,t) 就能达到割掉 (u,v) 的目的而使最小割变小。
类似的可以得出 (C_{u,v}geq C_{u,t}) , 那么只能是 (C_{u,v}=C_{u,t}) 。
用归纳法可以得到一个 (n) 个点的图中最多只有 (n-1) 个不同的最小割。
如何构建最小割树?
采用递归的策略 , 对于当前点集 , 任意取两个点做最小割(注意这里是对原图跑最小割) , 然后给这两个点连边 , 权值为最小割大小。
然后就把参与网络中与源点可达的点与源点扔在一起 , 与其他的和汇点扔在一起。两边递归即可。
正确性就是证明只有 (n-1) 个不同的最小割中的道理相同 , 考虑某一个点被划分在哪个集合从而保证了正确性。
代码:
cpp1:
#include<bits/stdc++.h>
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
#define Copy(a,b) memcpy(a,b,sizeof(a))
template<class T> inline void init(T&x){
x=0;char ch=getchar();bool t=0;
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
if(t) x=-x;
}
const int M=3020;
const int N=200;
const int INF=2e9;
struct edge{
int to,next,cap,flow;
}a[M<<1];
int head[N],cnt=0;
int que[N],n,m;
inline void add(int x,int y,int z){a[cnt]=(edge){y,head[x],z,z};head[x]=cnt++;}
int d[N],S,T,cur[N];
bool bel[N];queue<int> Q;
inline bool bfs(){
while(!Q.empty())Q.pop();
Set(d,0);d[S]=1;Q.push(S);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int v,i=head[u];~i;i=a[i].next){
v=a[i].to;if(d[v]||!a[i].cap) continue;
d[v]=d[u]+1;if(v==T) return 1;
Q.push(v);
}
}
return d[T];
}
int dfs(int u,int flow){
if(u==T) return flow;
int rest=flow;
for(int v,&i=cur[u];~i;i=a[i].next){
v=a[i].to;if(!a[i].cap||d[v]!=d[u]+1) continue;
int f=dfs(v,min(a[i].cap,rest));
if(!f) d[v]=0;
rest-=f;a[i].cap-=f,a[i^1].cap+=f;
if(!rest) break;
}
return flow-rest;
}
inline int Dinic(){
int flow=0;
while(bfs()) Copy(cur,head),flow+=dfs(S,INF);
return flow;
}
inline void Return(){for(int i=0;i<cnt;++i) a[i].cap=a[i].flow;for(int i=1;i<=n;++i) bel[i]=0;}
void Dfs(int u){bel[u]=1;for(int v,i=head[u];~i;i=a[i].next){v=a[i].to;if(a[i].cap&&!bel[v]) Dfs(v);}}
namespace GHT{
struct edge{int to,next,w;}a[N<<1];
int head[N],cnt=0;
inline void add(int x,int y,int z){a[++cnt]=(edge){y,head[x],z};head[x]=cnt;}
int tmp[N];
inline void Clear(){Set(head,0);cnt=0;}
void Build(int l,int r){
if(l>=r) return;
S=que[l],T=que[r];Return();int Flow=Dinic();Dfs(S);
int L=l-1,R=r+1;add(S,T,Flow),add(T,S,Flow);
for(int i=l;i<=r;++i) {int u=que[i];if(bel[u]) tmp[++L]=u;else tmp[--R]=u;}
for(int i=l;i<=r;++i) que[i]=tmp[i];
Build(l,L),Build(R,r);
return;
}
int gezi[N*N];
inline void DFS(int u,int fa,int Mi){
if(Mi!=INF) gezi[++gezi[0]]=Mi;
for(int v,i=head[u];i;i=a[i].next){
v=a[i].to;if(v==fa) continue;
DFS(v,u,min(Mi,a[i].w));
}
}
inline void work(){
for(int i=1;i<=n;++i) que[i]=i;
Build(1,n);gezi[0]=0;
for(int i=1;i<=n;++i) DFS(i,0,INF);
sort(gezi+1,gezi+1+gezi[0]);
int q;init(q);
while(q--){
int x;init(x);printf("%d
",(upper_bound(gezi+1,gezi+1+gezi[0],x)-gezi-1)/2);
}
puts("");
return;
}
}
int main()
{
int T;init(T);
while(T--){
Set(head,-1);cnt=0;GHT::Clear();
init(n),init(m);
int u,v,w;
for(int i=1;i<=m;++i) {
init(u),init(v),init(w);
add(u,v,w),add(v,u,w);
}
GHT::work();
}
return 0;
}
cpp2:
#include<bits/stdc++.h>
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
#define Copy(a,b) memcpy(a,b,sizeof(a))
template<class T> inline void init(T&x){
x=0;char ch=getchar();bool t=0;
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
if(t) x=-x;
}
const int M=8501;
const int N=1000;
const int INF=2e9;
struct edge{
int to,next,cap,flow;
}a[M<<1];
int head[N],cnt=0;
int que[N],n,m;
inline void add(int x,int y,int z){a[cnt]=(edge){y,head[x],z,z};head[x]=cnt++;}
int d[N],S,T,cur[N];
bool bel[N];queue<int> Q;
inline bool bfs(){
while(!Q.empty())Q.pop();
Set(d,0);d[S]=1;Q.push(S);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int v,i=head[u];~i;i=a[i].next){
v=a[i].to;if(d[v]||!a[i].cap) continue;
d[v]=d[u]+1;if(v==T) return 1;
Q.push(v);
}
}
return d[T];
}
int dfs(int u,int flow){
if(u==T) return flow;
int rest=flow;
for(int v,&i=cur[u];~i;i=a[i].next){
v=a[i].to;if(!a[i].cap||d[v]!=d[u]+1) continue;
int f=dfs(v,min(a[i].cap,rest));
if(!f) d[v]=0;
rest-=f;a[i].cap-=f,a[i^1].cap+=f;
if(!rest) break;
}
return flow-rest;
}
inline int Dinic(){
int flow=0;
while(bfs()) Copy(cur,head),flow+=dfs(S,INF);
return flow;
}
inline void Return(){for(int i=0;i<cnt;++i) a[i].cap=a[i].flow;for(int i=1;i<=n;++i) bel[i]=0;}
void Dfs(int u){bel[u]=1;for(int v,i=head[u];~i;i=a[i].next){v=a[i].to;if(a[i].cap&&!bel[v]) Dfs(v);}}
namespace GHT{
struct edge{int to,next,w;}a[N<<1];
int head[N],cnt=0;
inline void add(int x,int y,int z){a[++cnt]=(edge){y,head[x],z};head[x]=cnt;}
int tmp[N];
void Build(int l,int r){
if(l>=r) return;
S=que[l],T=que[r];Return();int Flow=Dinic();Dfs(S);
int L=l-1,R=r+1;add(S,T,Flow),add(T,S,Flow);
for(int i=l;i<=r;++i) {int u=que[i];if(bel[u]) tmp[++L]=u;else tmp[--R]=u;}
for(int i=l;i<=r;++i) que[i]=tmp[i];
Build(l,L),Build(R,r);
return;
}
map<int,int>vis;
int ans=0;
inline void DFS(int u,int fa,int Mi){
if(Mi!=INF) {if(!vis.count(Mi)) vis[Mi]=1,++ans;}
for(int v,i=head[u];i;i=a[i].next){
v=a[i].to;if(v==fa) continue;
DFS(v,u,min(Mi,a[i].w));
}
}
inline void work(){
for(int i=1;i<=n;++i) que[i]=i;
Build(1,n);
for(int i=1;i<=n;++i) DFS(i,0,INF);
cout<<ans<<endl;
return;
}
}
int main()
{
Set(head,-1);
init(n),init(m);
int u,v,w;
for(int i=1;i<=m;++i) {
init(u),init(v),init(w);
add(u,v,w),add(v,u,w);
}
GHT::work();
return 0;
}