1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ar(x) array<int,x>
const int N=500+10,M=1500+10,INF=1e9;
#define gc getchar()
#define rd read()
inline int read(){
int x=0,f=0; char c=gc;
for(;c<'0'||c>'9';c=gc) f|=(c=='-');
for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
int n,m,id[N],_id[N];
vector<ar(2)> G[N];
int head[N],ne[M*4],v[M*4],fl[M*4],tot=1;
void add(int x,int y,int f){
ne[++tot]=head[x],head[x]=tot,v[tot]=y,fl[tot]=f;
ne[++tot]=head[y],head[y]=tot,v[tot]=x,fl[tot]=0;
}
int s,t,dis[N],cur[N]; queue<int> q;
int bfs(){
for(int i=1;i<=n;++i) dis[i]=-1,cur[i]=head[i];
while(!q.empty()) q.pop(); q.push(s),dis[s]=0;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=head[u];i;i=ne[i]){
if(dis[v[i]]==-1&&fl[i]){
dis[v[i]]=dis[u]+1,q.push(v[i]);
if(v[i]==t) return 1;
}
}
}
return 0;
}
int dinic(int u,int df){
if(u==t) return df; int res=df;
for(int i=cur[u];res&&i;i=ne[i]){
cur[u]=i;
if(dis[v[i]]==dis[u]+1&&fl[i]){
int k=dinic(v[i],min(res,fl[i]));
if(!k) dis[v[i]]=-1;
else res-=k,fl[i]-=k,fl[i^1]+=k;
}
}
return df-res;
}
void sol(int l,int r){
if(l>=r) return;
int dflow=0,maxflow=0,_l=l-1,_r=r+1; s=id[l],t=id[r];
while(bfs()) while(dflow=dinic(s,INF)) maxflow+=dflow; bfs();
G[id[l]].pb({id[r],maxflow}),G[id[r]].pb({id[l],maxflow});
for(int i=2;i<=tot;i+=2) fl[i]+=fl[i^1],fl[i^1]=0;
for(int i=l;i<=r;++i){
if(dis[id[i]]!=-1) _id[++_l]=id[i];
else _id[--_r]=id[i];
}
for(int i=l;i<=r;++i) id[i]=_id[i];
sol(l,_l),sol(_r,r);
}
int tmp[N],ans[N][N];
void dfs(int u,int fu,int mn){ tmp[u]=mn; for(auto [v,w]:G[u]) if(v!=fu) dfs(v,u,min(mn,w)); }
int main(){
n=rd+1,m=rd;
for(int i=1;i<=n;++i) id[i]=i;
for(int i=1,x,y,z;i<=m;++i) x=rd+1,y=rd+1,z=rd,add(x,y,z),add(y,x,z);
sol(1,n);
for(int i=1;i<=n;++i) dfs(i,0,INF),memcpy(ans[i],tmp,4*(n+1));
m=rd; for(int i=1;i<=m;++i) printf("%d\n", ans[rd+1][rd+1]);
return 0;
}
|