您的位置: 首页  >  IT文章  >  [专题总结]最大权闭合子图和上下界网络流基础

[专题总结]最大权闭合子图和上下界网络流基础

分类: IT文章 • 2022-08-26 12:38:33

一页板子题。里面也有难的。但是建图不是特别复杂，*听到NC喊标签然后就AC了。

植物大战僵尸：

最大权闭合子图，挺板子的。

考虑一下每个植物都会保护它身后的植物，然后成环的保护关系一个都不能吃。

然后就是板子。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<vector>
 4 using namespace std;
 5 #define S 3333333
 6 vector<int>v[999];
 7 int n,m,val[999],ord[33][33],pc,Fir[999],L[S],To[S],deg[999],q[S],Ec,tp[999];
 8 int ec=1,fir[999],l[S],to[S],w[S],E,d[999],ans;
 9 bool bfs(){
10     for(int i=1;i<=E;++i)d[i]=0;
11     for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(w[i]&&!d[to[i]])
12         d[q[++t]=to[i]]=d[q[h]]+1;
13     return d[E];
14 }
15 int dfs(int p,int flow){int r=flow;
16     if(p==E)return flow;
17     for(int i=fir[p];i&&r;i=l[i])if(d[to[i]]==d[p]+1&&w[i]){
18         int x=dfs(to[i],min(w[i],r));
19         if(!x)d[to[i]]=0;
20         w[i]-=x;w[i^1]+=x;r-=x;
21     }return flow-r;
22 }
23 void Link(int a,int b){L[++Ec]=Fir[a];Fir[a]=Ec;To[Ec]=b;deg[b]++;}
24 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;w[ec]=V;}
25 void con(int a,int b,int V){link(a,b,V);link(b,a,0);}
26 int main(){
27     scanf("%d%d",&n,&m);
28     for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)ord[i][j]=++pc;E=++pc;
29     for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
30         int N,x,y;scanf("%d%d",&val[ord[i][j]],&N);
31         for(int p=1;p<=N;++p)scanf("%d%d",&x,&y),v[ord[i][j]].push_back(ord[x+1][y+1]);
32         if(j^1)v[ord[i][j]].push_back(ord[i][j-1]);
33     }
34     for(int i=1;i<pc;++i)for(int j=0;j<v[i].size();++j)Link(i,v[i][j]);
35     int t=1;
36     for(int i=1;i<pc;++i)if(!deg[i])q[++t]=i;
37     for(int h=2;h<=t;tp[q[h]]=1,++h)for(int i=Fir[q[h]];i;i=L[i]){
38         deg[To[i]]--;if(!deg[To[i]])q[++t]=To[i];
39     }
40     for(int i=1;i<pc;++i)if(tp[i]){
41         if(val[i]>0)con(0,i,val[i]),ans+=val[i];else con(i,E,-val[i]);
42         for(int j=0;j<v[i].size();++j)if(tp[v[i][j]])con(v[i][j],i,S);
43     }
44     while(bfs())ans-=dfs(0,S);printf("%d
",ans);
45 }
View Code

寿司餐厅

（颓标签之后）最大神的一个？

一定要好好看题啊不然想到暴毙也想不出来。

同一种寿司吃多次只会付出一次代价！！！（是同一种，不是同一个代号）

不然没法做。

现在就是对于每个区间只会获得一次收益，对于每种寿司只会付出一次代价，对于同一个代号的寿司只会付出一次代价。

比较明显的是，

1，如果你吃了区间[l,r]那么你一定也吃了[l,r-1]与[l+1,r]。就是区间的包含关系。

这种关系有传递性，在最大权闭合子图里不必考虑别的了。

2，然后如果你吃了[l,l]那么你就是吃了这种寿司，不管吃了几次都付出$a_i$代价。

3，如果你吃了x这种寿司，那么就表示你一定吃过代号为$a_x$的寿司，不管吃了几种几个都付出$a_x^2 imes m$代价

根据上面这3种关系建边就可以满足题意。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 #define S 6666666
 5 int fir[S],l[S],to[S],v[S],cur[S],ec=1,pc,o[111][111],a[111],n,m,d[S],q[S],E,O[1111],ans;
 6 bool bfs(){
 7     for(int i=0;i<=pc;++i)cur[i]=fir[i],d[i]=0;d[0]=1;
 8     for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&!d[to[i]])
 9         d[q[++t]=to[i]]=d[q[h]]+1;
10     return d[E];
11 }
12 int dfs(int p,int flow){int r=flow;
13     if(p==E)return r;
14     for(int i=cur[p];i&&r;i=l[i])if(v[i]&&d[to[i]]==d[p]+1){
15         cur[p]=i;int x=dfs(to[i],min(r,v[i]));
16         if(!x)d[to[i]]=0;
17         v[i]-=x;v[i^1]+=x;r-=x;
18     }return flow-r;
19 }
20 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;}
21 void con(int a,int b,int V=S){link(a,b,V);link(b,a,0);}
22 void add(int a,int V){if(V>0)con(0,a,V),ans+=V;else con(a,E,-V);}
23 int main(){
24     scanf("%d%d",&n,&m);
25     for(int i=1;i<=n;++i)scanf("%d",&a[i]);
26     for(int i=1;i<=n;++i)if(!O[a[i]])O[a[i]]=++pc;
27     for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)o[i][j]=++pc;
28     for(int i=1;i<=n;++i)con(o[i][i],O[a[i]]);
29     E=++pc;
30     for(int i=1;i<=1000;++i)if(O[i])add(O[i],-i*i*m);
31     for(int i=1,x;i<=n;++i){
32         scanf("%d",&x);x-=a[i];add(o[i][i],x);
33         for(int j=i+1;j<=n;++j)scanf("%d",&x),add(o[i][j],x),con(o[i][j],o[i+1][j]),con(o[i][j],o[i][j-1]);
34     }
35     while(bfs())ans-=dfs(0,S);printf("%d
",ans);
36 }
View Code

矩阵

其实挺板子的。不要想麻烦。《土兵占领》套个上下界就是这道题。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 #define S 11111111
 5 int x[205],y[205],n,m,R,L,fir[S],l[S],to[S],v[S],q[S],d[S],ec,SS,SE,E,cur[S],deg[S],tot;
 6 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;}
 7 void con(int a,int b,int V){link(a,b,V);link(b,a,0);}
 8 void add(int p,int f){if(f)if(f>0)con(p,SE,f);else con(SS,p,-f),tot-=f;}
 9 bool bfs(){
10     for(int i=0;i<=SE;++i)d[i]=0,cur[i]=fir[i];d[q[1]=SS]=1;
11     for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&!d[to[i]])
12         d[q[++t]=to[i]]=d[q[h]]+1;
13     return d[SE];
14 }
15 int dfs(int p,int flow){int r=flow;
16     if(p==SE)return r;
17     for(int i=cur[p];r&&i;i=l[i])if(v[i]&&d[to[i]]==d[p]+1){
18         cur[p]=i;int x=dfs(to[i],min(r,v[i]));
19         if(!x)d[to[i]]=0;
20         v[i]-=x;v[i^1]+=x;r-=x;
21     }return flow-r;
22 }
23 bool chk(int X){
24     for(int i=0;i<=SE;++i)fir[i]=deg[i]=0;ec=1;tot=0;
25     for(int i=1;i<=n;++i)con(0,i,x[i]+X-max(0,x[i]-X)),deg[i]-=max(0,x[i]-X),deg[0]+=max(0,x[i]-X);
26     for(int i=1;i<=m;++i)con(i+n,E,y[i]+X-max(0,y[i]-X)),deg[i+n]+=max(0,y[i]-X),deg[E]-=max(0,y[i]-X);
27     for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)con(i,j+n,R-L),deg[i]+=L,deg[j+n]-=L;
28     for(int i=0;i<=E;++i)add(i,deg[i]);
29     con(E,0,0x3fffffff);
30     while(bfs())tot-=dfs(SS,S);
31     return !tot;
32 }
33 int main(){
34     scanf("%d%d",&n,&m);SS=n+m+2;SE=SS+1;E=SS-1;
35     for(int i=1;i<=n;++i)for(int j=1,z;j<=m;++j)scanf("%d",&z),x[i]+=z,y[j]+=z;
36     scanf("%d%d",&L,&R);
37     int l=0,r=100000,ans;
38     while(l<=r)if(chk(l+r>>1))ans=r=l+r>>1,r--;else l=(l+r>>1)+1;
39     printf("%d
",ans);
40 }
View Code

支线剧情

有源汇上下界最小费用可行流。算是板子。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 #define S 33333
 5 int ans,n,fir[S],l[S],to[S],v[S],w[S],ec=1,deg[S],d[S],q[S],iq[S],al[S];
 6 void link(int a,int b,int V,int W){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;w[ec]=W;}
 7 void con(int a,int b,int W){link(a,b,S,W);link(b,a,0,-W);}
 8 bool SPFA(){
 9     for(int i=1;i<=n+2;++i)d[i]=S;
10     for(int h=1,t=1;h<=t;iq[q[h]]=0,++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&d[to[i]]>d[q[h]]+w[i]){
11         d[to[i]]=d[q[h]]+w[i];
12         if(!iq[to[i]])iq[q[++t]=to[i]]=1;
13     }return d[n+2]<S;
14 }
15 int dfs(int p,int flow){int r=flow;
16     if(p==n+2)return r;al[p]=1;
17     for(int i=fir[p];i&&r;i=l[i])if(d[to[i]]==d[p]+w[i]&&v[i]&&!al[to[i]]){
18         int x=dfs(to[i],min(v[i],r));
19         if(!x)d[to[i]]=S;
20         v[i]-=x;v[i^1]+=x;r-=x;ans+=w[i]*x;
21     }al[p]=0;return flow-r;
22 }
23 int main(){
24     scanf("%d",&n);
25     for(int i=1,x,y,c;i<=n;++i){scanf("%d",&x);while(x--)scanf("%d%d",&y,&c),con(i,y,c),deg[i]++,deg[y]--,ans+=c;}
26     for(int i=2;i<=n;++i)if(deg[i])if(deg[i]>0)link(i,n+2,deg[i],0),link(n+2,i,0,0);else link(0,i,-deg[i],0),link(i,0,0,0);
27     for(int i=1;i<=n;++i)con(i,n+1,0);
28     con(n+1,1,0);
29     while(SPFA())dfs(0,S);printf("%d
",ans);
30 }
View Code

志愿者招募

每一种志愿者服务的时间是一段连续的区间。于是想到对于每个时间单位拆点连边，卡住下届。

每一种志愿者就是边被，从l连向r没有意义。于是尝试从r连向l-1。

这样的话每个志愿者就对应一个环。这个图没有源汇，有上下界和费用。

听到NC说了标签，于是就剩下一个无源汇上下界最小费用可行流。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 #define int long long
 5 #define inf 0x3fffffffffffff
 6 int n,m,fir[1005],l[66666],to[66666],v[66666],w[66666],q[66666],iq[1005],ec=1,deg[1005],S,E,ans,d[1005],al[1005];
 7 void link(int a,int b,int V,int c){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;w[ec]=c;}
 8 void con(int a,int b,int V,int c){link(a,b,V,c);link(b,a,0,-c);}
 9 bool bfs(){
10     for(int i=0;i<=E;++i)d[i]=inf;d[q[1]=S]=0;
11     for(int h=1,t=1;h<=t;iq[q[h]]=0,++h)for(int i=fir[q[h]];i;i=l[i])if(d[to[i]]>d[q[h]]+w[i]&&v[i]){
12         d[to[i]]=d[q[h]]+w[i];
13         if(!iq[to[i]])iq[q[++t]=to[i]]=1;
14     }return d[E]!=inf;
15 }
16 int dfs(int p,int flow){
17     if(p==E)return flow;int r=flow;al[p]=1;
18     for(int i=fir[p];i&&r;i=l[i])if(!al[to[i]]&&v[i]&&d[to[i]]==d[p]+w[i]){
19         int x=dfs(to[i],min(r,v[i]));
20         if(!d[to[i]])d[to[i]]=inf;
21         v[i]-=x;v[i^1]+=x;ans+=x*w[i];r-=x;
22     }al[p]=0;return flow-r;
23 }
24 main(){
25     scanf("%lld%lld",&n,&m);S=n+1;E=S+1;
26     for(int i=1,x;i<=n;++i)scanf("%lld",&x),con(i-1,i,inf,0),deg[i]-=x,deg[i-1]+=x;
27     for(int i=1,l,r,c;i<=m;++i)scanf("%lld%lld%lld",&l,&r,&c),con(r,l-1,inf,c);
28     for(int i=0;i<=n;++i)if(deg[i])if(deg[i]>0)con(i,E,deg[i],0);else con(S,i,-deg[i],0);
29     while(bfs())dfs(S,inf);
30     printf("%lld
",ans);
31 }
View Code

旅行时的困惑

上下界有源汇最小流。就是正向可行流再逆向最大流（尽量退流）

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 #define Z 888888
 5 int n,fir[Z],l[Z],to[Z],v[Z],d[Z],q[Z],deg[Z],S,E,ec=1,ans,cur[Z];
 6 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;}
 7 void con(int a,int b){link(a,b,Z);link(b,a,0);}
 8 bool bfs(){
 9     for(int i=0;i<=n+3;++i)d[i]=0,cur[i]=fir[i];d[q[1]=S]=1;
10     for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(!d[to[i]]&&v[i])
11         d[q[++t]=to[i]]=d[q[h]]+1;
12     return d[E];
13 }
14 int dfs(int p,int flow){int r=flow;
15     if(p==E)return r;
16     for(int i=cur[p];i&&r;i=l[i])if(d[to[i]]==d[p]+1&&v[i]){
17         int x=dfs(to[i],min(v[i],r));
18         if(!x)d[to[i]]=0,cur[p]=l[i];
19         v[i]-=x;v[i^1]+=x;r-=x;
20         if(!v[i])cur[p]=l[i];
21     }return flow-r;
22 }
23 int main(){
24     scanf("%d",&n);
25     for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),x++,y++,con(x,y),deg[x]++,deg[y]--;
26     for(int i=1;i<=n;++i)con(0,i),con(i,n+1);con(n+1,0);S=n+2;E=n+3;
27     for(int i=1;i<=n;++i)if(deg[i])if(deg[i]>0)link(i,E,deg[i]),link(E,i,0);else link(S,i,-deg[i]),link(i,S,0);
28     while(bfs())dfs(S,Z);
29     for(int i=fir[0];i;i=l[i])if(v[i]>700000)ans+=Z-v[i];else if(to[i]==n+1)v[i]=v[i^1]=0;
30     S=n+1;E=0;while(bfs())ans-=dfs(S,Z);printf("%d
",ans);
31 }
View Code

清理雪道

同上。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int n,fir[111],l[66666],to[66666],d[111],v[66666],w[111],S,E,q[111],ans,ec=1;
 5 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;}
 6 void con(int a,int b){link(a,b,66666);link(b,a,0);}
 7 bool bfs(){
 8     for(int i=0;i<=n+3;++i)d[i]=0;d[q[1]=S]=1;
 9     for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(!d[to[i]]&&v[i])
10         d[q[++t]=to[i]]=d[q[h]]+1;
11     return d[E];
12 }
13 int dfs(int p,int flow){int r=flow;
14     if(p==E)return r;
15     for(int i=fir[p];i&&r;i=l[i])if(v[i]&&d[to[i]]==d[p]+1){
16         int x=dfs(to[i],min(r,v[i]));
17         if(!x)d[to[i]]=0;
18         v[i]-=x;v[i^1]+=x;r-=x;
19     }return flow-r;
20 }
21 int main(){
22     scanf("%d",&n);
23     for(int i=1,x,y;i<=n;++i){scanf("%d",&x);while(x--)scanf("%d",&y),con(i,y),w[i]++,w[y]--;}
24     for(int i=1;i<=n;++i)con(0,i),con(i,n+1);
25     con(n+1,0);S=n+2;E=n+3;
26     for(int i=0;i<=n+1;++i)if(w[i])if(w[i]>0)link(i,E,w[i]),link(E,i,0);else link(S,i,-w[i]),link(i,S,0);
27     while(bfs())dfs(S,66666);
28     for(int i=fir[0];i;i=l[i])if(v[i]>60000)ans+=66666-v[i];
29     S=n+1;E=0;
30     for(int i=fir[S];i;i=l[i])if(!to[i]&&v[i]>60000)v[i]=v[i^1]=0;
31     while(bfs())ans-=dfs(S,66666);
32     printf("%d
",ans);
33 }
View Code

相关推荐