@[林国盛](/user/261370) %%%小六切黑题
by cnyzz @ 2020-03-07 14:02:12
Orz
by LongDouble @ 2020-03-07 14:02:53
注意：lz还只是个小学六年级的，让我们一起%他
by LongDouble @ 2020-03-07 14:04:54
tpl
by cnyzz @ 2020-03-07 14:06:21
```cpp
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int n,m,q;
namespace network{
queue<int>q;
struct tu{
int to,pre,f;
}edge[6001];
int tot=1,head[501],dep[501];
inline void add(int x,int y,int z){
edge[++tot].to=y;
edge[tot].pre=head[x];
edge[tot].f=z;
head[x]=tot;
}
inline void insert(int x,int y,int z){
add(x,y,z);
add(y,x,0);
}
inline bool bfs(int s,int t){
while(!q.empty())q.pop();
memset(dep,0,sizeof(dep));
q.push(s);
dep[s]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].pre){
int node=edge[i].to;
if(dep[node]||!edge[i].f)continue;
dep[node]=dep[x]+1;
q.push(node);
}
}
return dep[t];
}
inline int dfs(int x,int t,int flow){
if(x==t)return flow;
int rest=flow;
for(int i=head[x];i;i=edge[i].pre){
int node=edge[i].to;
if(dep[node]!=dep[x]+1||!edge[i].f)continue;
int y=dfs(node,t,min(edge[i].f,rest));
if(!y)dep[node]=0;
edge[i].f-=y;
edge[i^1].f+=y;
rest-=y;
if(rest==0)return flow;
}
return flow-rest;
}
inline void init(){
for(int i=2;i<=tot;i++){
edge[i].f=edge[i].f+edge[i^1].f;
edge[i^1].f=0;
}
}
inline int dinic(int s,int t){
init();
int ans=0;
while(bfs(s,t)){
int x;
while(x=dfs(s,t,INF))ans+=x;
//printf("%d\n",ans);
}
return ans;
}
}
namespace tree{
struct tu{
int to,pre,f;
}edge[1000];
int tot,head[501],dep[501],lg,node[501]
,minn[20][501],father[20][501];
inline void add(int x,int y,int z){
edge[++tot].to=y;
edge[tot].f=z;
edge[tot].pre=head[x];
head[x]=tot;
}
inline void insert(int x,int y,int z){
add(x,y,z);
add(y,x,z);
}
inline void bulid(int l,int r){
if(l==r)return;
int s=node[l],t=node[l+1];
int cut=network::dinic(s,t);
insert(s,t,cut);
int cnt=0,num=0,temp1[501],temp2[501];
for(int i=l;i<=r;i++){
if(network::dep[node[i]])temp1[++cnt]=node[i];
else temp2[++num]=node[i];
}
for(int i=l;i<=l+cnt-1;i++)node[i]=temp1[i-l+1];
for(int i=l+cnt;i<=r;i++)node[i]=temp2[i-l-cnt+1];
bulid(l,l+cnt-1);
bulid(l+cnt,r);
}
inline void dfs(int x,int fa){
dep[x]=dep[fa]+1;
father[0][x]=fa;
for(int i=1;i<=lg;i++){
father[i][x]=father[i-1][father[i-1][x]];
minn[i][x]=min(minn[i-1][x],minn[i-1][father[i-1][x]]);
}
for(int i=head[x];i;i=edge[i].pre){
if(edge[i].to==fa)continue;
minn[0][edge[i].to]=edge[i].f;
dfs(edge[i].to,x);
}
}
inline void pre(){
lg=log(n)/log(2)+1;
for(int i=1;i<=n;i++)node[i]=i;
bulid(1,n);
dfs(1,0);
}
inline int query(int x,int y){
int ans=INF;
if(dep[x]!=dep[y]){
if(dep[x]<dep[y])swap(x,y);
for(int i=lg;i>=0;i--){
if(dep[father[i][x]]>=dep[y]){
ans=min(ans,minn[i][x]);
x=father[i][x];
}
}
}
if(x==y)return ans;
for(int i=lg;i>=0;i--){
if(father[i][x]!=father[i][y]){
ans=min(ans,min(minn[i][x],minn[i][y]));
x=father[i][x],y=father[i][y];
}
}
return min(ans,min(minn[0][x],minn[0][y]));
}
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
network::insert(x,y,z);
network::insert(y,x,z);
}
tree::pre();
scanf("%d",&q);
while(q--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",tree::query(x,y));
}
return 0;
}
```
by Andy_Lin @ 2020-03-07 14:54:57
已AC
by Andy_Lin @ 2020-03-07 14:55:15
我一个初一的看到这个帖子之后，就知道我被单调队列掉了
by Prean @ 2020-04-06 18:31:10