Question chain :

http://www.lydsy.com/JudgeOnline/problem.php?id=2229

Answer key :

First, take a look at this blog :http://blog.csdn.net/jyxjyx27/article/details/42750833
Very good , We can have a simple perceptual knowledge of minimal cut trees .

It's very troublesome to find the minimum cut tree , And the number of points in this question is not large ,
So there is no need to construct a minimum cut tree , Just figure out all the ans[i][j]:i->j The minimum cut .
That is, divide and conquer , Find out n-1 A minimal cut ,
And after every minimal cut , Try to update the ans that will do .

Code :

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 200
#define MAXM 7000
#define INF 0x3f3f3f3f
#define filein(x) freopen(#x".in","r",stdin);
#define fileout(x) freopen(#x".out","w",stdout);
using namespace std;
struct Edge{
int to[MAXM],cap[MAXM],next[MAXM],head[MAXN],ent;
void Init(){
ent=2; memset(head,0,sizeof(head));
}
void Adde(int u,int v,int w){
to[ent]=v; cap[ent]=w; next[ent]=head[u]; head[u]=ent++;
to[ent]=u; cap[ent]=0; next[ent]=head[v]; head[v]=ent++;
}
void reset(){
for(int i=2;i<ent;i+=2){
cap[i]=cap[i^1]=(cap[i]+cap[i^1])/2;
}
}
}E;
bool mark[MAXN];
int a[MAXN],cur[MAXN],d[MAXN],ans[MAXN][MAXN];
int N,M,Q;
bool bfs(int S,int T){
static queue<int> q; int u,v;
memset(d,0,sizeof(d));
d[S]=1; q.push(S);
while(!q.empty()){
u=q.front(); q.pop();
for(int i=E.head[u];i;i=E.next[i]){
v=E.to[i];
if(d[v]||!E.cap[i]) continue;
d[v]=d[u]+1; q.push(v);
}
}
return d[T];
}
int dfs(int u,int reflow,const int &T){
if(u==T||!reflow) return reflow;
int flowout=0,f,v;
for(int &i=cur[u];i;i=E.next[i]){
v=E.to[i];
if(d[v]!=d[u]+1) continue;
f=dfs(v,min(reflow,E.cap[i]),T);
flowout+=f; E.cap[i^1]+=f;
reflow-=f; E.cap[i]-=f;
if(!reflow) break;
}
if(!flowout) d[u]=0;
return flowout;
}
int Dinic(int S,int T){
int flow=0;
while(bfs(S,T)){
memcpy(cur,E.head,sizeof(E.head));
flow+=dfs(S,INF,T);
}
return flow;
}
void dfs(int u){
mark[u]=1;
for(int i=E.head[u];i;i=E.next[i])
if(!mark[E.to[i]]&&E.cap[i]) dfs(E.to[i]);
}
void Partition(int l,int r){
static int tmp[MAXN],S,T,cut;
if(l>=r) return;
E.reset(); S=a[l]; T=a[r];
cut=Dinic(S,T);
memset(mark,0,sizeof(mark)); dfs(S);
for(int i=1;i<=N;i++)
for(int j=1;j<i;j++) if(mark[a[i]]^mark[a[j]])
ans[a[i]][a[j]]=ans[a[j]][a[i]]=min(ans[a[i]][a[j]],cut);
int L=l,R=r;
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<L;i++) a[i]=tmp[i];
for(int i=r;i>R;i--) a[i]=tmp[i];
Partition(l,L-1);
Partition(R+1,r);
}
int main()
{
filein(mincut); fileout(mincut);
int T; scanf("%d",&T);
while(T--){
E.Init();
memset(ans,0x3f,sizeof(ans));
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) a[i]=i;
for(int i=1,u,v,w;i<=M;i++){
scanf("%d%d%d",&u,&v,&w);
E.Adde(u,v,2*w);
}
E.reset(); Partition(1,N);
scanf("%d",&Q);
for(int k=1,c,num;k<=Q;k++){
scanf("%d",&c); num=0;
for(int i=1;i<=N;i++)
for(int j=1;j<i;j++)
if(ans[i][j]<=c) num++;
printf("%d\n",num);
}
puts("");
} return 0;
}

●BOZJ 2229 [Zjoi2011] More articles on minimal cuts

  1. bzoj 2229 [Zjoi2011] Minimum cut ( Divide and conquer + Minimum cut )

    [ Topic link ] http://www.lydsy.com/JudgeOnline/problem.php?id=2229 [ The question ] Answer a number of questions about cuts no more than x Point to point number inquiry . [ Ideas ] [ The minimum cut has the maximum n ...

  2. bzoj 2229: [Zjoi2011] Minimum cut

    Description Xiaobai learned a new concept in graph theory class -- Minimum cut , After class, Xiaobai wrote the following paragraph in his notebook : " For a picture , A partition of nodes in a graph divides all nodes in the graph into two parts , If the node s,t Not at the same time ...

  3. BZOJ.2229.[ZJOI2011] Minimum cut ( Minimum tree cutting )

    Topic link The question : Given an undirected graph , Find the minimum cut between any two points . Select any two of all the points as the source point \(S\). Confluence \(T\), Find the minimum cut between them \(ans\), And divide the original image into two point sets \(S',T'\), use \(ans ...

  4. bzoj 2229: [Zjoi2011] Minimum cut 【Gomory–Hu tree Minimum tree cutting 】

    This algorithm is shown in http://www.cnblogs.com/lokiii/p/8191573.html After finding the minimum cut between two, we can calculate the violence statistics #include<iostream> #inclu ...

  5. 2229: [Zjoi2011] Minimum cut ( Minimum tree cutting )

    Description Xiaobai learned a new concept in graph theory class —— Minimum cut , After class, Xiaobai wrote the following paragraph in his notebook : “ For a picture , A partition of nodes in a graph divides all nodes in the graph into two parts , If the node s,t Not in the same section ...

  6. BZOJ2229: [Zjoi2011] Minimum cut

    Answer key : It's a magic question !!! We are still watching JZP Let's solve the problem ( The web address can't be found ...) Code : #include<cstdio> #include<cstdlib> #include&l ...

  7. bzoj The thousand questions project 139:bzoj2229: [Zjoi2011] Minimum cut

    http://www.lydsy.com/JudgeOnline/problem.php?id=2229 Introduction to minimum cut tree :http://blog.csdn.net/jyxjyx27/article/de ...

  8. bzoj2229: [Zjoi2011] Minimum cut ( Divide and conquer minimum cut + The idea of minimum cut tree )

    2229: [Zjoi2011] Minimum cut subject : Portal Answer key : A very good topic !!! The idea of konjac : Violent enumeration point to run minimum cut record ... Absolutely explosive .... I began to wonder if the title was deceptive ... Don't you use network flow at all ?? ...

  9. 【BZOJ2229】[ZJOI2011] Minimum cut ( Network flow , Minimum tree cutting )

    [BZOJ2229][ZJOI2011] Minimum cut ( Network flow , Minimum tree cutting ) Topic BZOJ Luogu Answer key Poke it here So the implementation process is to choose any two points to run the minimum cut to update the answer , And then divide the set of points into and \(S\) Connect with and \(T\) Unicom . ...

Random recommendation

  1. [SHOI2008] Traffic jams traffic

    I'm Mengmeng's portal To put it bluntly, this is a graph connectivity maintenance that supports adding and deleting edges , But in view of the particularity of graphs , You can directly segment the tree ( It's said that this is the standard calculation --). But I'm lazy , I don't want to think about how to segment trees , So I wrote a division and collection ,1A I am ...

  2. One a day linux command (26): use SecureCRT To upload and download files

    use SSH management linux The server often needs remote and local interactive files . And direct use SecureCRT Its own upload and download function is undoubtedly the most convenient ,SecureCRT The file transfer protocol under ASCII.Xmodem.Zmodem. ...

  3. Use Maven Build a multi module project

    [ turn ] Use Maven Build a multi module project In normal times Javaweb In the development of the project, for the convenience of later maintenance , We usually develop in layers , The most common is divided into domain( Domain model layer ).dao( Database access layer ).service( Business ...

  4. Talking about storage in simple terms : How to distinguish NAS、SAN And DAS

    Talking about storage in simple terms : How to distinguish NAS.SAN And DAS 2012 year 02 month 17 Japan 16:51 source : Sina blog   author : Lin peiman edit : Zeng Zhiqiang   View full text Fabulous (0) Comment on (1)  Share label : DAS , SAN , Storage system ...

  5. Android Handler Summary of ways to avoid memory leaks

    Android Development often uses handler, But we find that every time we use it Handler Will appear :This Handler class should be static or leaks might occur ...

  6. android The implementation of the boot page And jump to the main page

    first activity package com.qualitypicture.activity; import java.util.ArrayList; import java.util.List; ...

  7. bzoj1449————2016——3——14

    Portal :http://www.lydsy.com/JudgeOnline/problem.php?id=1449 A brief introduction to the topic : Description Input Output An integer represents all the balls in the League ...

  8. Script executable , But there is no HTML Test report file generation , The cause is in PyCharm Execution mode error

    Define two ways to write a test report : 1) Test reports are generated directly under the local absolute path # Import HTMLTestRunner modular import HTMLTestRunner # adopt open() Method in binary write mode ('wb') hit ...

  9. JavaSE Learning summary ( Two )——Java Language foundation

    One .Java Program preview Java Grammar and C Very similar , Here are a few very simple procedures to distinguish between point and area C language Java Let's talk about each knowledge point in detail . This article only aims at the friend who has the programming foundation to refer to . 1.1.Hello World establish j ...

  10. MySQL Disaster recovery online master-slave replication becomes master master replication and multi-source replication 【 turn 】

    Production master copy (A<--->B), And disaster recovery master-slave replication (B--->C). When there is a problem in production , Data writing is switched to the disaster recovery database , After production is resumed , Write disaster recovery back to production . Steps are as follows : 1. Disaster recovery and production, one of which is to establish the main ...