BZOJ2229

#include 
     
      #include 
      
       #include 
       
        using namespace std;    int cnt,nd[151],dep[151],sor,tar,dl[151],cur[151],sta[10001],mark[151],a[151],n,ans[151][151],tmp[151],m;    struct edge{      int next,des,cap,fr;  }sid[10001];    void addedge2(int u,int v,int cap){      sid[cnt].next=nd[u];sid[cnt].des=v;sid[cnt].cap=cap;nd[u]=cnt;sid[cnt].fr=u;cnt++;      sid[cnt].next=nd[v];sid[cnt].des=u;sid[cnt].cap=cap;nd[v]=cnt;sid[cnt].fr=v;cnt++;  }      int bfs(){      memset(dep,-1,sizeof(dep));            int head=1,tail=1;      dep[sor]=0;dl[head]=sor;      while (head<=tail){        for (int p=nd[dl[head]];p!=-1;p=sid[p].next)          if ((dep[sid[p].des]==-1)&&(sid[p].cap)) dep[sid[p].des]=dep[dl[head]]+1,dl[++tail]=sid[p].des;        head++;      }        if (dep[tar]==-1) return(0);else return(1);   }      int dinic(){      int maxflow=0;      while (bfs()){          for (int i=1;i<=n;i++) cur[i]=nd[i];                    int u=sor,top=0;            while(1){              if (u==tar){                  int mi=1e9,last;                  for (int i=1;i<=top;i++)                    if (sid[sta[i]].cap
        
         >1;   }  void dfs(int po){      mark[po]=1;      for (int p=nd[po];p!=-1;p=sid[p].next)        if (sid[p].cap&&!mark[sid[p].des])          dfs(sid[p].des);  }  void solve(int l,int r){      if (l==r) return;      restore();      sor=a[l];tar=a[r];      int flow=dinic();            for (int i=1;i<=n;i++) mark[i]=0;      dfs(sor);      for (int i=1;i<=n;i++) if (mark[i])        for (int j=1;j<=n;j++) if (!mark[j])          ans[i][j]=ans[j][i]=min(ans[i][j],flow);      int pol=l-1,por=r+1;    for (int i=l;i<=r;i++)               if (mark[a[i]]) tmp[++pol]=a[i];else tmp[--por]=a[i];    for (int i=l;i<=r;i++) a[i]=tmp[i];    solve(l,pol);solve(por,r);    }  int main(){            int T;      scanf("%d",&T);      while (T--){        scanf("%d%d",&n,&m);cnt=0;      for (int i=1;i<=n;i++) nd[i]=-1,a[i]=i;      for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)        ans[i][j]=1e9;      for (int i=1;i<=m;i++){          int t1,t2,t3;          scanf("%d%d%d",&t1,&t2,&t3);          addedge2(t1,t2,t3);      }      solve(1,n);      int q;      scanf("%d",&q);      while (q--){          int lim,tans=0;          scanf("%d",&lim);          for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++)            if (ans[i][j]<=lim) tans++;          printf("%d",tans);if (q!=0||T!=0) printf("\n");      }      if (T!=0) printf("\n");    }  }