NC20495. [ZJOI2011]最小割
描述
输入描述
输入文件第一行有且只有一个正整数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
输出:
10
C++(g++ 7.5.0) 解法, 执行用时: 129ms, 内存消耗: 1104K, 提交时间: 2022-12-31 11:00:54
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 210, M = 3010 * 4, INF = 0x3f3f3f3f;
// 边数要开四倍
int h[N], e[M], ne[M], f[M], idx, d[N], n, m, S, T, cur[M];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}
bool bfs()
{
queue<int>q;
memset(d, -1, sizeof d);
q.push(S);
d[S] = 0;
cur[S] = h[S];
while(!q.empty())
{
auto t = q.front();
q.pop();
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if((d[j] == -1) && f[i])
{
d[j] = d[t] + 1;
cur[j] = h[j];
if(j == T) return true;
q.push(j);
}
}
}
return false;
}
int find(int u, int limit)
{
if(u == T) return limit;
int flow = 0;
for(int i = cur[u]; ~i && flow < limit; i = ne[i])
{
int j = e[i];
cur[u] = i;
if((d[j] == d[u] + 1) && f[i])
{
int t = find(j, min(f[i], limit - flow));
if(!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
for(int i = 0; i < idx; i += 2) f[i] += f[i ^ 1], f[i ^ 1] = 0; // 退流
int r = 0, flow;
while(bfs()) while(flow = find(S, 0x3f3f3f3f)) r += flow;
return r;
}
int id[N], ans[N][N], tmp1[N], tmp2[N];
void work(int l, int r)
{
if(l == r) return;
S = id[l], T = id[l + 1];
int t = dinic(), s = id[l], tt = id[l + 1];
ans[S][T] = ans[T][S] = t;
int cnt1 = 0, cnt2 = 0;
for(int i = l; i <= r; i ++ )
if(d[id[i]] != -1) tmp1[++ cnt1] = id[i];
else tmp2[++ cnt2] = id[i];
for(int i = 1; i <= cnt1; i ++ ) id[i + l - 1] = tmp1[i];
for(int i = 1; i <= cnt2; i ++ ) id[cnt1 + l + i - 1] = tmp2[i];
work(l, l + cnt1 - 1);
work(l + cnt1, r);
for(int i = 1; i <= cnt1; i ++)
for(int j = 1; j <= cnt2; j ++ )
{
int a = id[i + l - 1], b = id[j + cnt1 + l - 1];
ans[b][a] = ans[a][b] = min({ans[a][s], ans[s][tt], ans[tt][b]});
}
}
void solve()
{
cin >> n >> m;
memset(h, -1, sizeof h);
idx = 0;
memset(ans, 0x3f, sizeof ans);
for(int i = 1; i <= m; i ++ )
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
for(int i = 1; i <= n; i ++ ) id[i] = i;
work(1, n);
int q;
cin >> q;
while(q -- )
{
int x, res = 0;
cin >> x;
for(int i = 1; i <= n; i ++ )
for(int j = i + 1; j <= n; j ++ ) if(ans[i][j] <= x) res ++;
cout << res << '\n';
}
cout << '\n';
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while(T -- ) solve();
}
C++ 解法, 执行用时: 90ms, 内存消耗: 596K, 提交时间: 2022-07-04 22:16:46
#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define LL long long
#define maxn 155
#define maxm 6005
using namespace std;
inline void read(int &a){
char c;while(!isdigit(c=getchar()));
for(a=c-'0';isdigit(c=getchar());a=a*10+c-'0');
}
const int inf = 0x3f3f3f3f;
int n,m,S,T;
int fir[maxn],cur[maxn],dis[maxn],nxt[maxm],to[maxm],tot=1,cap[maxm],sum;
inline void line(int x,int y,int z,int rz=0){
nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,cap[tot]=z;
nxt[++tot]=fir[y],fir[y]=tot,to[tot]=x,cap[tot]=rz;
}
queue<int>q;
bool bfs()
{
memset(dis,0,(n+1)<<2);
dis[T]=1,q.push(T);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=fir[u];i;i=nxt[i]) if(cap[i^1]&&!dis[to[i]]){
dis[to[i]]=dis[u]+1;
q.push(to[i]);
}
}
return dis[S];
}
int dfs(int u,int lim)
{
if(u==T) return lim;
int need=lim,delta;
for(int &i=cur[u];i;i=nxt[i]) if(cap[i]&&dis[u]==dis[to[i]]+1){
delta=dfs(to[i],min(cap[i],need));
cap[i]-=delta,cap[i^1]+=delta;
if(!(need-=delta)) break;
}
return lim-need;
}
int Dinic(){
int flow=0;
while(bfs()) memcpy(cur,fir,(n+1)<<2),flow+=dfs(S,inf);
return flow;
}
int Test,Q,x,y,z,s,ans[maxn][maxn],id[maxn],tmp[maxn];
void solve(int l,int r){
if(l>=r) return;
for(int i=2;i<=tot;i+=2) cap[i]=cap[i+1]=(cap[i]+cap[i+1])>>1;
S=id[l],T=id[r];
int ret=Dinic();
for(int i=1;i<=n;i++) if(dis[i])
for(int j=1;j<=n;j++) if(!dis[j])
ans[i][j]=ans[j][i]=min(ans[i][j],ret);
int h=l-1,t=r;
for(int i=l;i<=r;i++) if(dis[id[i]]) tmp[++h]=id[i]; else tmp[t--]=id[i];
for(int i=l;i<=r;i++) id[i]=tmp[i];
solve(l,h),solve(h+1,r);
}
signed main()
{
read(Test);
while(Test--)
{
memset(fir,0,sizeof fir),tot=1;
memset(ans,0x3f,sizeof ans);
read(n),read(m);
for(int i=1;i<=m;i++) read(x),read(y),read(z),line(x,y,z,z);
for(int i=1;i<=n;i++) id[i]=i;
solve(1,n);
read(Q);
while(Q--){
read(x),s=0;
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(ans[i][j]<=x) s++;
printf("%d\n",s);
}
puts("");
}
}