Processing math: 100%

BZOJ2276:[Poi2011]Temperature 单调性+线段树

10 年前

思路:

貌似存在O(n)的算法,不过由于我太弱只想到了O(nlogn).

现在很困就发代码了...有问题回复找我吧.

?
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
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define N 1000010
struct SegmentTree{
    int a[2100000],M;
    inline void Init(int _siz){
        for(M=1;M<(_siz+2);M<<=1);
        memset(a,0xc0,sizeof a);
    }
    inline void upd(int x,int to){
        for(a[x+=M]=to,x>>=1;x;x>>=1)a[x]=max(a[x<<1],a[x<<1^1]);
    }
    inline int ask(int tl,int tr){
        int res=-1<<30;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if(~tl&1)res=max(res,a[tl^1]);
            if(tr&1)res=max(res,a[tr^1]);
        }return res;
    }
}Seg;
  
int up[N];
  
namespace Fio{
    inline int getc(){
#ifndef ONLINE_JUDGE
        static const int L=1<<1;
#else
        static const int L=1<<15;
#endif
        static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}return*S++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c=0;while(!digit(c=getc())&&c!='-');bool sign=c=='-';x=sign?0:c-'0';
        while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';if(sign)x=-x;
    }
}
  
int main(){
    int n;Fio::Get(n);register int i,j;
    Seg.Init(n);
    int x;for(i=1;i<=n;++i)Fio::Get(x),Fio::Get(up[i]),Seg.upd(i,x);
      
    int nowmax=Seg.ask(1,1);
    int lans,ans;
    for(lans=2;lans<=n;++lans){
        if(nowmax>up[lans])break;
        nowmax=max(nowmax,Seg.ask(lans,lans));
    }ans=--lans;
      
    for(i=2;i<=n;++i){
        nowmax=Seg.ask(i,lans);
        for(++lans;lans<=n;++lans){
            if(nowmax>up[lans])break;
            nowmax=max(nowmax,Seg.ask(lans,lans));
        }--lans;
        ans=max(ans,lans-i+1);
    }
      
    printf("%d",ans);
      
    return 0;
}

 

Tags: 单调性 线段树
Posted in BZOJ | 0 Comments

BZOJ1821:[JSOI2010]Group 部落划分 Group 二分+并查集

10 年前

思路:

我保证这是一种奇葩算法.

我们二分答案,那么问题就转化为若任意两个部落之间的距离≤l,是否能够划分为为k组.

我们能发现以下性质:若能够划分为k′组,且满足k′>k,则必定能够划分为k组.原因是我们可以合并一些块,那么部落之间距离的最小值必然不会减少.

因此我们只需考虑对于一个给定的l,最多能够划分为几组.

考虑两个点,若两点距离≤l,那么必定划分在一组中.那么现在有若干个连通块,不同连通块之间的所有点的距离均>l,显然当前连通块数就是我们要求的最大连通块数.

于是二分+并查集水.

?
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
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
  
#define N 1010
int n,k,x[N],y[N],r[N];
  
inline void init(){for(int i=1;i<=n;++i)r[i]=i;}
inline int find(int x){int q=x,rq;for(;x!=r[x];x=r[x]);for(;q!=x;q=rq)rq=r[q],r[q]=x;return x;}
inline void merge(int x,int y){r[find(x)]=find(y);}
typedef double f2;
  
f2 dis(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
  
  
int main(){
    scanf("%d%d",&n,&k);register int i,j;
    for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
      
    f2 Maxdis=0;
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)Maxdis=max(Maxdis,dis(i,j));
      
    f2 L=0,R=Maxdis,mid;
    while(R-L>1e-4){
        mid=(L+R)*.5;
        init();
        for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(dis(i,j)<=mid)merge(i,j);
          
        int cnt=0;for(i=1;i<=n;++i)cnt+=(i==find(i));
          
        if(cnt>=k)L=mid;else R=mid;
    }
      
    printf("%.2lf",L);
      
    return 0;
}

Tags: 二分 并查集
Posted in BZOJ | 0 Comments

BZOJ2144:跳跳棋 LCA

10 年前

思路:

对于一个状态(x,y,z)(x<y<z),我们发现可行的操作仅有三种:

(1)将y向左移动

(2)将y向右移动

(3)将x,z中离y比较近的一个以y为中心移动.(当y−x=z−y时不能这样做)

 

那么有人就要问了,还有离y比较远的以y为中心移动的情况呢?这必然与(1)(2)中的一个等价.

 

因此,我们可以将状态建成一棵树,对于一个状态,(1)(2)得到的是这个状态的左右儿子,(3)得到的是这个状态的父亲.

 

那么就很容易处理了.我们类似寻找LCA的过程不断向上爬即可.但我们不是暴力的向上找父亲,而是发现连续的若干次找父亲其实就是一个做gcd的过程.利用Euclid加速即可.

?
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
83
84
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
  
typedef long long LL;
  
struct Pos{
    int x,y,z;
    Pos(){}
    Pos(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
    bool operator!=(const Pos&B)const{return x!=B.x||y!=B.y||z!=B.z;}
    bool operator==(const Pos&B)const{return x==B.x&&y==B.y&&z==B.z;}
};
  
LL updep;
inline Pos up(int x,int y,int z,LL d){
    if(d==0)return Pos(x,y,z);
    if(y-x==z-y)return Pos(x,y,z);
    int d1=y-x,d2=z-y,step;
    if(d1>d2){
        if(d1%d2==0){
            step=d1/d2-1;
            if(d<=step)return updep+=d,Pos(x,x+d1-d*d2,x+d1-d*d2+d2);
            else return updep+=step,up(x,x+d2,x+2*d2,d-step);
        }
        else{
            step=d1/d2;
            if(d<=step)return updep+=d,Pos(x,x+d1-d*d2,x+d1-d*d2+d2);
            else return updep+=step,up(x,x+d1%d2,x+d1%d2+d2,d-step);
        }
    }
    else{
        if(d2%d1==0){
            step=d2/d1-1;
            if(d<=step)return updep+=d,Pos(z-(d2-d*d1)-d1,z-(d2-d*d1),z);
            else return updep+=step,up(z-2*d1,z-d1,z,d-step);
        }
        else{
            step=d2/d1;
            if(d<=step)return updep+=d,Pos(z-(d2-d*d1)-d1,z-(d2-d*d1),z);
            else return updep+=step,up(z-d2%d1-d1,z-d2%d1,z,d-step);
        }
    }
}
inline Pos up(const Pos&p,LL d){return up(p.x,p.y,p.z,d);}
  
inline void Sort(int&x,int&y,int&z){
    int d[3]={x,y,z};sort(d,d+3);x=d[0],y=d[1],z=d[2];
}
  
int main(){
    int x1,y1,z1,x2,y2,z2;
    scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);Sort(x1,y1,z1),Sort(x2,y2,z2);
  
    LL dep1,dep2;
    updep=0;Pos Root1=up(x1,y1,z1,1<<30);dep1=updep;
    updep=0;Pos Root2=up(x2,y2,z2,1<<30);dep2=updep;
  
    if(Root1!=Root2)puts("NO");
    else{
        puts("YES");
        if(dep1<dep2)swap(dep1,dep2),swap(x1,x2),swap(y1,y2),swap(z1,z2);
        Pos now1=up(x1,y1,z1,dep1-dep2),now2=Pos(x2,y2,z2);
  
        if(now1==now2)printf("%d",dep1-dep2);
        else{
            int L=0,R=dep2,mid;
            while(L<R){
                mid=(L+R+1)>>1;
                if(up(now1,mid)!=up(now2,mid))L=mid;else R=mid-1;
            }
            printf("%d",dep1-dep2+2*(L+1));
        }
    }
#ifndef ONLINE_JUDGE
    system("pause");
#endif
  
    return 0;
}

 

Tags: LCA
Posted in BZOJ | 0 Comments

BZOJ1143:[CTSC2008]祭祀river(&&BZOJ2718) 二分图

10 年前

思路:

首先是一个DAG.

然后,你要选出最多的点,使得任意两个点之间不能有到达关系.

考虑将拓扑图划分为若干条点不相交路径,那么所有的结束点之间都是不能到达的.

那么我们就要求出DAG的最小路径覆盖.

然而事实上由于是DAG,路径的点是可以相交的.于是我们通过拆点转化为一般的点不相交最小路径覆盖.

考虑给每一个点找一个入点,那么每出现一个匹配,路径的数目就会减少1.

于是利用总点数减去最大匹配即可.

?
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
#define _CRT_SECURE_NO_WARNINGS
 
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
 
#define INF 0x3f3f3f3f
 
#define N 210
struct MaxflowSolver{
    static const int V=N<<1;
    static const int E=N*N<<1;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V],gap[V],stk[V],top,cur[V];
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int res=0,u=S,i,Min,ins;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find)cur[u]=stk[top++]=ins,u=end[ins];
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}SteinsGate;
 
int head[N],next[N*N],end[N*N];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
 
int seq[N],cnt;bool vis[N];
void dfs(int x){
    vis[x]=1,seq[++cnt]=x;
    for(int j=head[x];j;j=next[j])if(!vis[end[j]])dfs(end[j]);
}
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    int a,b;while(m--)scanf("%d%d",&a,&b),addedge(a,b);
 
    SteinsGate.reset();
    for(i=1;i<=n;++i){
        memset(vis,0,sizeof vis);
        cnt=0,dfs(i);
        for(j=1;j<=cnt;++j)if(seq[j]!=i)SteinsGate.make(i,n+seq[j],1);
    }
 
    int S=0,T=2*n+1;
    for(i=1;i<=n;++i)SteinsGate.make(0,i,1);
    for(i=1;i<=n;++i)SteinsGate.make(n+i,T,1);
 
    printf("%d",n-SteinsGate.Maxflow(S,T,2*n+2));
 
#ifndef ONLINE_JUDGE
    system("pause");
#endif
    return 0;
}

Tags: 二分图
Posted in BZOJ | 0 Comments

BZOJ2229:[Zjoi2011]最小割 最小割树

10 年前

思路:

无向图的任意两点之间的最小割可以用一颗树来表示.

构造方法:

在当前的连通集合中任取两点(若当前连通集合仅有一个点退出),并在原图中求这两点之间的最小割.

在最小割树上连接这两个点,边权为刚才求出的最小割.

将当前的连通集合根据刚才的割划分为两部分,递归处理.

 

求出最小割树之后,两个点之间的最小割即为最小割树上两个点之间的路径上的边权最小值.

 

这道题就这样水就行了.

?
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cstdlib>
#include<iostream>
using namespace std;
  
#define INF 0x3f3f3f3f
  
#define N 160
int n,m,G[N][N];
  
struct MaxflowSolver{
    int head[N],next[N*N<<1],end[N*N<<1],flow[N*N<<1],ind;
    int d[N],gap[N],stk[N],top,cur[N];
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline void make2(int a,int b,int f){addedge(a,b,f),addedge(b,a,f);}
    inline void bfs(int T){
        static int q[N];int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int Min,ins,res=0,i,u=S;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find)stk[top++]=cur[u]=ins,u=end[ins];
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}Curse;
  
struct Graph{
    int head[N],next[N*N<<1],end[N*N<<1],ind;
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q;}
    inline void make(int a,int b){addedge(a,b),addedge(b,a);}
}SteinsGate;
  
int totalState[N],totalid;bool totalvis[N];
void dfs(int x){
    totalvis[x]=1,totalState[++totalid]=x;
    for(int j=SteinsGate.head[x];j!=-1;j=SteinsGate.next[j])if(!totalvis[SteinsGate.end[j]])dfs(SteinsGate.end[j]);
}
  
struct Tree{
    int head[N],next[N<<1],end[N<<1],len[N<<1],ind;
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int l){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,len[q]=l;}
    inline void make(int a,int b,int l){addedge(a,b,l),addedge(b,a,l);}
}T;
  
int inS[N],q[N],fr,ta;
void Solve(int State[],int n){
    if(n==1)return;
      
    register int i,j;
    Curse.reset();
    for(i=1;i<=totalid;++i)for(j=i+1;j<=totalid;++j)if(G[totalState[i]][totalState[j]])
        Curse.make2(totalState[i],totalState[j],G[totalState[i]][totalState[j]]);
      
    int res=Curse.Maxflow(State[1],State[2],totalid);
      
    T.make(State[1],State[2],res);
      
    memset(inS,0,sizeof inS);fr=ta=0;q[ta++]=State[1];
    while(fr^ta){
        i=q[fr++];inS[i]=1;for(j=Curse.head[i];j!=-1;j=Curse.next[j])if(Curse.flow[j]&&!inS[Curse.end[j]])q[ta++]=Curse.end[j];
    }
      
    int seql[N],numl=0,seqr[N],numr=0;
    for(i=1;i<=n;++i)if(inS[State[i]])seql[++numl]=State[i];else seqr[++numr]=State[i];
      
    Solve(seql,numl);
    Solve(seqr,numr);
}
  
int ans[N][N];
inline void getans(int anc,int x,int fa,int nowans){
    ans[anc][x]=nowans;
    for(int j=T.head[x];j!=-1;j=T.next[j])if(T.end[j]!=fa)getans(anc,T.end[j],x,min(T.len[j],nowans));
}
  
int seq[N*N],nums;
int main(){
    int Tec;scanf("%d",&Tec);register int i,j;int a,b,x;
    while(Tec--){
        scanf("%d%d",&n,&m);
        memset(G,0,sizeof G);while(m--)scanf("%d%d%d",&a,&b,&x),G[a][b]+=x,G[b][a]+=x;
        SteinsGate.reset();for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(G[i][j])SteinsGate.make(i,j);
          
        memset(totalvis,0,sizeof totalvis);
        T.reset();
        for(i=1;i<=n;++i)if(!totalvis[i]){
            totalid=0;
            dfs(i);
              
            Solve(totalState,totalid);
        }
          
        nums=0;
        for(i=1;i<=n;++i){
            getans(i,i,-1,INF);
            for(j=i+1;j<=n;++j)seq[++nums]=ans[i][j];
        }
          
        int Q;scanf("%d",&Q);
        while(Q--){
            scanf("%d",&x);
            int res=0;for(i=1;i<=nums;++i)if(seq[i]<=x)++res;
            printf("%d\n",res);
        }
        puts("");
          
    }
      
    return 0;
}

Tags: 最小割树
Posted in BZOJ | 0 Comments

BZOJ3218:a + b Problem 网络流+线段树

10 年前

思路:

首先最小割的建模是显然的.

令S集合表示选择白色,T集合表示选择黑色.

则有:

S−>i c=wi表示割掉这条边之后,i在T集合,颜色为黑色,失去了白色的价值.

同理i−>T c=bi.

接下来假设有一堆点,若这些点有一个为白色,且i为黑色,则损失价值pi.

这个怎么搞?

设一个辅助节点x,让所有对i有影响的点j都连j−>x c=INF.然后再连接x−>i c=pi.

这样的话,如果有某个点x选了白色(属于S集),而节点i为黑色(属于T集),那么这条pi的边就必定需要割掉.

 

可是这样边数爆表.

注意到一堆INF的边很是浪费,于是我们用线段树优化.

首先不考虑标号的限制,只考虑l≤a≤r的限制.

离散化后,我们用线段树上的O(logn)个节点来连向辅助节点.

 

接下来是标号的限制...

我们用一颗可持久化线段树来维护连边即可.

(关于可持久化线段树的姿势可以看代码)

(内附良心样例)

?
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<map>
using namespace std;
   
#define INF 0x3f3f3f3f
   
#define N 5010
int a[N],b[N],w[N],l[N],r[N],p[N];
   
int seq[N*3],id;
   
struct MaxflowSolver{
    int head[300010],next[1000010],end[1000010],flow[1000010],ind;
    int d[300010],gap[300010],cur[300010],stk[300010],top;
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){/*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[300010];int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int res=0,i,Min,ins,u=S;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find){cur[u]=stk[top++]=ins,u=end[ins];}
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}SteinsGate;
   
struct Node{
    int l,r;
}S[300010];int cnt;
   
int root[5010];
int Newversion(int last,int tl,int tr,int ins){
    int q=++cnt;S[q]=S[last];if(last)SteinsGate.make(last,q,INF);if(tl==tr)return q;
    int mid=(tl+tr)>>1;
    if(ins<=mid)S[q].l=Newversion(S[last].l,tl,mid,ins);else S[q].r=Newversion(S[last].r,mid+1,tr,ins);
    return q;
}
   
void Addedge(int q,int tl,int tr,int dl,int dr,int topoint){
    if(dl<=tl&&tr<=dr){if(q)SteinsGate.make(q,topoint,INF);return;}
    int mid=(tl+tr)>>1;
    if(dr<=mid)Addedge(S[q].l,tl,mid,dl,dr,topoint);
    else if(dl>mid)Addedge(S[q].r,mid+1,tr,dl,dr,topoint);
    else Addedge(S[q].l,tl,mid,dl,mid,topoint),Addedge(S[q].r,mid+1,tr,mid+1,dr,topoint);
}
   
int main(){
    int n;scanf("%d",&n);register int i,j;
    for(i=1;i<=n;++i)scanf("%d%d%d%d%d%d",&a[i],&b[i],&w[i],&l[i],&r[i],&p[i]);
   
    for(i=1;i<=n;++i)seq[++id]=a[i],seq[++id]=l[i],seq[++id]=r[i];sort(seq+1,seq+id+1);
    map<int,int>M;int num=0;for(seq[0]=-1<<30,i=1;i<=id;++i)if(seq[i]!=seq[i-1])M[seq[i]]=++num;
    for(i=1;i<=n;++i)a[i]=M[a[i]],l[i]=M[l[i]],r[i]=M[r[i]];
   
    SteinsGate.reset();
    for(i=1;i<=n;++i)root[i]=Newversion(root[i-1],1,num,a[i]),SteinsGate.make(250000+i,cnt,INF);
    for(i=1;i<=cnt;++i){
        if(S[i].l)SteinsGate.make(S[i].l,i,INF);
        if(S[i].r)SteinsGate.make(S[i].r,i,INF);
    }
   
    int S=0,T=++cnt,res=0;
    for(i=1;i<=n;++i)res+=b[i]+w[i],SteinsGate.make(S,250000+i,w[i]),SteinsGate.make(250000+i,T,b[i]);
    for(i=1;i<=n;++i)if(i)Addedge(root[i-1],1,num,l[i],r[i],++cnt),SteinsGate.make(cnt,250000+i,p[i]);
   
    printf("%d",res-SteinsGate.Maxflow(S,T,cnt+1+n));
   
#ifndef ONLINE_JUDGE
    system("pause");
#endif
   
    return 0;
}
/*10
0 1 7 3 9 2
7 4 0 9 10 5
1 0 4 2 10 2
7 9 1 5 7 2
6 3 5 3 6 2
6 6 4 1 8 1
6 1 6 0 6 5
2 2 5 0 9 3
5 1 3 0 2 5
5 6 7 1 1 2*/

 

Tags: 网络流 可持久化线段树
Posted in BZOJ | 0 Comments

BZOJ3772:精神污染 dfs序+可持久化线段树

10 年前

以后决定土豪题都粘一下题面吧.

【begin

Description

兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游，为了方便，他们在县内的N个旅游景点上建立了n-1条观光道，构成了一棵图论中的树。同时他们推出了M条观光线路，每条线路由两个节点x和y指定，经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。
你和你的朋友打算前往兵库县旅游，但旅行社还没有告知你们最终选择的观光线路是哪一条（假设是线路A）。这时候你得到了一个消息：在兵库北有一群丧心病狂的香菜蜜，他们已经选定了一条观光线路（假设是线路B），对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路，比如有四个景点1-2-3-4，而【精神污染】的路径是1-4，那么1-3,2-4,1-2等路径也被视为被完全污染了。
现在你想知道的是，假设随便选择两条不同的路径A和B，存在一条路径使得如果这条路径被污染，另一条路径也被污染的概率。换句话说，一条路径被另一条路径包含的概率。
 

 

Input

第一行两个整数N,M
接下来N-1行，每行两个数a,b，表示A和B之间有一条观光道。
接下来M行，每行两个数x,y，表示一条旅游线路。
 

 

Output

所求的概率，以最简分数形式输出。
 

 

Sample Input

5 3
1 2
2 3
3 4
2 5
3 5
2 5
1 4

Sample Output

1/3
样例解释
可以选择的路径对有(1,2),(1,3),(2,3)，只有路径1完全覆盖路径2。

HINT

 

100%的数据满足：N,M<=100000

end】

思路:

分类讨论几种完全覆盖的情形,然后用离线+dfs序+可持久化线段树水过.时间复杂度O(mlogn).

真的想写的话自己看代码.

?
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
  
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    inline bool digit(int x){return x>='0'&&x<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
  
#define N 100010
int n,m;
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
  
int pa[N][17],dep[N],in[N],out[N],tclock;
void dfs(int x,int fa){
    in[x]=++tclock;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){pa[end[j]][0]=x,dep[end[j]]=dep[x]+1,dfs(end[j],x);}
    out[x]=tclock;
}
inline int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=16;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=16;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
  
#define M 100010
int x[M],y[M],Lca[M];
  
vector<int>v[N];
  
int root[N<<1];
struct SegmentTree{
    struct Node{
        int l,r,siz;
    }S[3000000];
    int cnt;
    inline void reset(){cnt=0;}
    inline int newnode(){int q=++cnt;S[q].l=S[q].r=S[q].siz=0;return q;}
    int Newversion(int Last,int tl,int tr,int ins){
        int q=newnode();S[q]=S[Last],++S[q].siz;if(tl==tr)return q;
        int mid=(tl+tr)>>1;
        if(ins<=mid)S[q].l=Newversion(S[Last].l,tl,mid,ins);else S[q].r=Newversion(S[Last].r,mid+1,tr,ins);
        return q;
    }
    inline int Query(int q,int tl,int tr,int dl,int dr){
        if(dl>dr)return 0;
        if(dl<=tl&&tr<=dr){return S[q].siz;}
        int mid=(tl+tr)>>1;
        if(dr<=mid)return Query(S[q].l,tl,mid,dl,dr);
        else if(dl>mid)return Query(S[q].r,mid+1,tr,dl,dr);
        else return Query(S[q].l,tl,mid,dl,mid)+Query(S[q].r,mid+1,tr,mid+1,dr);
    }
}Seg;
  
struct Path{
    int x,y;
    Path(){}
    Path(int _x,int _y):x(_x),y(_y){}
}sav[M<<1];
inline bool cmp1(const Path&A,const Path&B){return in[A.x]<in[B.x];}
inline bool cmp2(const Path&A,const Path&B){return in[A.y]<in[B.y];}
  
int seq[M<<1];
long long res;
  
void calcstep1(){
    register int i;int lans,rans,L,R,mid;
    for(int Root=1;Root<=n;++Root){
        int num=(int)v[Root].size();if(!num)continue;
        for(i=1;i<=num;++i){sav[i]=Path(x[v[Root][i-1]],y[v[Root][i-1]]);if(in[sav[i].x]>in[sav[i].y])swap(sav[i].x,sav[i].y);}
        sort(sav+1,sav+num+1,cmp1);
        Seg.reset();
        for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].y]);
        for(i=1;i<=num;++i)seq[i]=in[sav[i].x];
        for(i=1;i<=num;++i){
            if(in[sav[i].x]>seq[num]||out[sav[i].x]<seq[1])continue;
            for(L=1,R=num;L<R;){
                mid=(L+R)>>1;
                if(seq[mid]>=in[sav[i].x])R=mid;else L=mid+1;
            }lans=L;
            for(L=1,R=num;L<R;){
                mid=(L+R+1)>>1;
                if(seq[mid]>out[sav[i].x])R=mid-1;else L=mid;
            }rans=L;
            res+=Seg.Query(root[rans],1,n,in[sav[i].y],out[sav[i].y])-Seg.Query(root[lans-1],1,n,in[sav[i].y],out[sav[i].y])-1;
        }
    }
}
  
void calcstep2(){
    register int i;int lans,rans,L,R,mid,num=0;
    for(i=1;i<=m;++i){      
        if(x[i]==Lca[i]||y[i]==Lca[i]){sav[++num]=Path(x[i],y[i]);if(in[sav[num].x]>in[sav[num].y])swap(sav[num].x,sav[num].y);}
    }
    sort(sav+1,sav+num+1,cmp2);
    Seg.reset();
    for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].x]);
    for(i=1;i<=num;++i)seq[i]=in[sav[i].y];
    for(i=1;i<=num;++i){
        if(in[sav[i].y]>seq[num]||out[sav[i].y]<seq[1])continue;
        for(L=1,R=num;L<R;){
            mid=(L+R)>>1;
            if(seq[mid]>=in[sav[i].y])R=mid;else L=mid+1;
        }lans=L;
        for(L=1,R=num;L<R;){
            mid=(L+R+1)>>1;
            if(seq[mid]>out[sav[i].y])R=mid-1;else L=mid;
        }rans=L;
        res+=Seg.Query(root[rans],1,n,1,in[sav[i].x])+Seg.Query(root[rans],1,n,out[sav[i].x]+1,n);
        res-=Seg.Query(root[lans-1],1,n,1,in[sav[i].x])+Seg.Query(root[lans-1],1,n,out[sav[i].x]+1,n);
        res--;
    }
}
  
void calcstep3(){
    register int i;int lans,rans,L,R,mid,num=0;
    for(i=1;i<=m;++i)if(x[i]!=Lca[i]&&y[i]!=Lca[i])sav[++num]=Path(Lca[i],x[i]),sav[++num]=Path(Lca[i],y[i]);
    sort(sav+1,sav+num+1,cmp2);
    Seg.reset();
    for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].x]);
    for(i=1;i<=num;++i)seq[i]=in[sav[i].y];
    for(i=1;i<=m;++i){
        if(x[i]!=Lca[i]&&y[i]!=Lca[i])continue;
        if(in[x[i]]>in[y[i]])swap(x[i],y[i]);
        if(in[y[i]]>seq[num]||out[y[i]]<seq[1])continue;
        for(L=1,R=num;L<R;){
            mid=(L+R)>>1;
            if(seq[mid]>=in[y[i]])R=mid;else L=mid+1;
        }lans=L;
        for(L=1,R=num;L<R;){
            mid=(L+R+1)>>1;
            if(seq[mid]>out[y[i]])R=mid-1;else L=mid;
        }rans=L;
        res+=Seg.Query(root[rans],1,n,1,in[x[i]])+Seg.Query(root[rans],1,n,out[x[i]]+1,n);
        res-=Seg.Query(root[lans-1],1,n,1,in[x[i]])+Seg.Query(root[lans-1],1,n,out[x[i]]+1,n);
        if(x[i]==y[i])res-=(int)v[x[i]].size();
    }
}
  
long long gcd(long long a,long long b){return(!b)?a:gcd(b,a%b);}
  
int main(){
    Fio::Get(n),Fio::Get(m);register int i,j;int a,b;
    for(i=1;i<n;++i){
        Fio::Get(a),Fio::Get(b);make(a,b);
    }
    dep[1]=1,dfs(1,-1);for(j=1;j<=16;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
      
    for(i=1;i<=m;++i){
        Fio::Get(x[i]),Fio::Get(y[i]),Lca[i]=lca(x[i],y[i]);
        if(Lca[i]!=x[i]&&Lca[i]!=y[i])v[Lca[i]].push_back(i);
    }
      
    calcstep1();
    calcstep2();
    calcstep3();
      
    if(res==0)puts("0/1");
    else{
        long long total=(long long)m*(m-1)/2;
        long long Gcd=gcd(res,total);res/=Gcd,total/=Gcd;
        printf("%lld/%lld",res,total);
    }
      
    return 0;
}

Tags: DFS序 可持久化线段树
Posted in BZOJ | 1 Comments

BZOJ3632:外太空旅行 随机化算法

10 年前

思路:

直接随机出很多排列,然后按照顺序贪心加入当前的团,然后每一次更新答案.

不过这为什么是对的呢?

...

...

...

...

...

...

这个问题比较高深,等我变厉害了再来解释解释.

?
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
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
int G[51][51],seq[51],in[51];
int main(){
    int n;scanf("%d",&n);
    int a,b;while(scanf("%d%d",&a,&b)==2)G[a][b]=G[b][a]=1;
    register int i,j;
    for(i=1;i<=n;++i)seq[i]=i;
    int res=0;
    for(int T=1;T<=5000;++T){
        for(i=1;i<=n;++i)swap(seq[i],seq[rand()%i+1]);
        int nowans=0;memset(in,0,sizeof in);
        for(i=1;i<=n;++i){
            bool ok=1;
            for(j=1;j<i;++j)if(in[seq[j]]&&!G[seq[i]][seq[j]]){ok=0;break;}
            if(ok)in[seq[i]]=1,++nowans;
        }
        res=max(res,nowans);
    }
    printf("%d",res);
    return 0;
}

Tags: 随机化算法
Posted in BZOJ | 1 Comments

BZOJ3442:学习小组 费用流

10 年前

思路:

一开始YY了一个上下界最小费用流,结果有负圈...看来只有消圈姿势对才能搞了.

其实只有一个问题就是如何用最大流来限制参加的人数尽可能多,我们可以连接:

S−>i Maxcap=k Cost=0

i−>T Maxcap=k−1 Cost=0

这样就确保了最大流中每个人必定会走1的流量.

剩下的就水了.

?
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
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<algorithm>
#include<queue>
using namespace std;
  
#define INF 0x3f3f3f3f
  
int cnt;
struct CostFlowSolver{
    int head[210],next[2000010],end[2000010],flow[2000010],cost[2000010],ind;
    int d[210],ld[210],lb[210];bool inq[210];queue<int>q;
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q]=c;}
    inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);}
    inline bool spfa(int S,int T){
        memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S);
        while(!q.empty()){
            int i=q.front();q.pop(),inq[i]=0;for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                d[end[j]]=d[i]+cost[j],ld[end[j]]=i,lb[end[j]]=j;if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }return d[T]!=INF;
    }
    inline int Mincost(int S,int T){
        int res=0,Min,i;
        while(spfa(S,T)){for(Min=INF,i=T;i^S;i=ld[i])Min=min(Min,flow[lb[i]]);for(i=T;i^S;i=ld[i])flow[lb[i]]-=Min,flow[lb[i]^1]+=Min;res+=Min*d[T];}
        return res;
    }
}SteinsGate;
  
int c[110],f[110];
int main(){
    int n,m,k;scanf("%d%d%d",&n,&m,&k);register int i,j;
    for(i=1;i<=m;++i)scanf("%d",&c[i]);for(i=1;i<=m;++i)scanf("%d",&f[i]);
  
    cnt=n+m;int S=0,T=++cnt;
    SteinsGate.reset();
    for(i=1;i<=n;++i)SteinsGate.make(S,i,k,0);
    for(i=1;i<=n;++i)if(k>1)SteinsGate.make(i,T,k-1,0);
    int x;for(i=1;i<=n;++i)for(j=1;j<=m;++j){scanf("%1d",&x);if(x)SteinsGate.make(i,n+j,1,-f[j]);}
    for(j=1;j<=m;++j)for(i=1;i<=n;++i)SteinsGate.make(n+j,T,1,c[j]*(2*i-1));
  
    printf("%d",SteinsGate.Mincost(S,T));
    return 0;
}

Tags: 网络流
Posted in BZOJ | 0 Comments

BZOJ2502:清理雪道 上下界网络流

10 年前

思路:

比较一眼.

长了一个姿势,就是有源汇有上下界网络最小流求法.

首先求可行流,得到满足下界需要的流量,就是从原来的汇流回原来的源的流量(C1).

这不见得是最小的.

因此我们删去原来的源和原来的汇之间的边,再求一次从原来的汇到原来的源的最大流(C2),也即退掉尽可能多的流量.

由于下界是不会退流的.

显而易见(?).C1−C2就是答案.

据称有时候这样做还会出问题?

大家一起来围观Kanari神犇:详细的~~~~网址如下:

http://blog.csdn.net/huzecong/article/details/8631748

?
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
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
  
#define INF 0x3f3f3f3f
  
int cnt;
struct MaxflowSolver{
    int head[110],next[80010],end[80010],flow[80010],ind;
    int d[110],gap[110],stk[110],top,cur[110];
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[110];int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        int res=0,u=S,Min,ins,i;top=0,bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find){stk[top++]=cur[u]=ins,u=end[ins];}
            else{
                Min=cnt+1;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}SteinsGate;
  
int main(){
    int n;scanf("%d",&n);
    register int i,j;
    cnt=n;int SS=0,ST=++cnt,S=++cnt,T=++cnt;
      
    int t,x;SteinsGate.reset();
    for(i=1;i<=n;++i){
        SteinsGate.make(S,i,INF);
        SteinsGate.make(i,T,INF);
        scanf("%d",&t);
        while(t--)scanf("%d",&x),SteinsGate.make(SS,x,1),SteinsGate.make(i,ST,1),SteinsGate.make(i,x,INF);
    }
    SteinsGate.make(T,S,INF);
      
    int res;
    SteinsGate.Maxflow(SS,ST);
    for(j=SteinsGate.head[S];j!=-1;j=SteinsGate.next[j])if(SteinsGate.end[j]==T)res=SteinsGate.flow[j],SteinsGate.flow[j]=SteinsGate.flow[j^1]=0;
    printf("%d",res-SteinsGate.Maxflow(T,S));
      
    return 0;
}

Tags: 上下界网络流
Posted in BZOJ | 0 Comments