Lvat_s Blog

这题我写了很长很长时间。。。

SB错误1:无向图要建双向边，然而我只建了单向边……

SB"错误"2:要加当前弧优化！一开始偷懒没加，然后TLE了N次

分治最小割，直接上Gusfield算法

顺便庆祝lyz lyf wyx cjy大爷签了PKU一本线 太神了orzzzzzzzzzzzzz

我这种蒟蒻ZJOI完全不敢去……

要补一补ZJOI讲课的Gusfield和Stoer-wanger算法了

为什么重建边时直接均分流量是对的啊……我按照正常方法写的然后跑的奇慢无比

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;

const int N=3005,P=155;
const long long INF=210000000000000ll;

int n,m,en,h[P],q,level[P],S,T,a[P],mark[P],tmp[P],Data_Num,cur[P];
long long ans[P][P];
queue<int> Q;

struct Edges{
int a,b;
long long v;
}es[N];

struct Edge{
int b,next,back;
long long f;
}e[N*4];

void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
Q.push(S);
level[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
    for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}

long long DFS(int u,long long flow){
if(u==T)return flow;
long long f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    long long fl;
    if(level[u]+1==level[v] && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}

long long Dinic(){
long long ans=0;
while(BFS()){for(int i=1;i<=n;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}

void dfs(int u){
mark[u]=1;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(e[i].f && !mark[v])dfs(v);
}
}

void Build(){
en=0;
memset(h,0,sizeof(h));
for(int i=1;i<=m;i++)AddEdge(es[i].a,es[i].b,es[i].v),AddEdge(es[i].b,es[i].a,es[i].v);;
}

void Rebuild(){
for(int i=1;i<=en;i+=2){e[i].f=e[i+1].f+e[i].f;e[i+1].f=0;}
}

void Solve(int l,int r){
if(l==r)return;
Rebuild();S=a[l];T=a[r];
long long flow=Dinic();
int L=l,R=r;
memset(mark,0,sizeof(mark));
dfs(S);
for(int i=1;i<=n;i++){
	if(!mark[i])continue;
	for(int j=1;j<=n;j++){
		if(!mark[j])ans[i][j]=ans[j][i]=min(ans[i][j],flow);
	}
}
for(int i=l;i<=r;i++){
	if(mark[a[i]])tmp[L++]=a[i];
	else tmp[R--]=a[i];
}
for(int i=l;i<=r;i++)a[i]=tmp[i];
Solve(l,L-1);Solve(R+1,r);
}

int main(){
freopen("2229.in","r",stdin);
freopen("2229.out","w",stdout);
scanf("%d",&Data_Num);
while(Data_Num--){
	memset(ans,127,sizeof(ans));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d %d %lld",&es[i].a,&es[i].b,&es[i].v);
	for(int i=1;i<=n;i++)a[i]=i;
	Build();
	Solve(1,n);
	scanf("%d",&q);
	while(q--){
		int Ans=0;
		long long x;
		scanf("%lld",&x);
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(ans[i][j]<=x)Ans++;
			}
		}
		printf("%d\n",Ans);
	}
	puts("");
}
return 0;
}