首页 > 代码库 > bzoj3882 [Wc2015]K小割
bzoj3882 [Wc2015]K小割
Description
.png)
Input
Output
Sample Input
3 3 1 3 100
1 2 3
2 3 4
1 3 5
1 2 3
2 3 4
1 3 5
Sample Output
8
9
12
-1
9
12
-1
正解：暴搜+堆+最小割。
我觉得这道题真是毒瘤的可以了，正解要写$3$个程序才能过。。
$task1$：
$n<=10,m<=20$，暴搜即可。
$task2$：
$s$向除了$t$以外其他点连边，其他点向$t$连边。
最小割就是每个点的两条边取最小值然后相加。
考虑用堆来维护$k$小割，我们用类似于$k$短路的方法。
设每个点的两条边分别为$a$，$b$，且$a<=b$。
把每个点分为$3$级，$a$为$0$级，$b$为$1$级，$a+b$为$2$级。
我们作一个差，把$b-a$和$a$存起来，然后按照两个关键字从小到大排序。
我们发现，每个点只要升级就是加上$b-a$或$a$就行了。
那么对于每个点，有$3$种选择：
1.当前点升级；
2.当前点降级，后面那个点升级；
3.后面那个点升级。
然后就很好求出答案了。注意一个细节，就是操作$2$只在当前点为$1$级时考虑。因为从$2$级降到$1$级，后面那个点升级，这样会与操作$3$重复。
$task3$：
$n,m,k$不大，没有特殊条件。
我们直接考虑$k$小割如何求，我们得到最小割以后，然后有两种选择：要么是把最小割中的某一条边换成另一边，要么直接加一条边。
用类似$k$短路的做法，我们可以强制选一条边，或强制不选一条边，然后考虑上面两种生成次小割的方法。
直接加一条边就枚举不在割集的最小边加入就行了。
对于第一种情况，我们要删掉割集的一条边，那么显然要使$S,T$到两个割点必须不连通。
那么我们对于这两个割点，对$S,T$跑最小割，求出最小的最小割，然后加上这个最小割就行了。
不过细节巨多，所以我基本上是抄的代码。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define inf (1<<28) 14 #define il inline 15 #define RG register 16 #define ll long long 17 18 using namespace std; 19 20 struct E{ int u,v,w; }G[500010]; 21 22 int n,m,k,S,T,mx; 23 24 il int gi(){ 25 RG int x=0,q=1; RG char ch=getchar(); 26 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 27 if (ch==‘-‘) q=-1,ch=getchar(); 28 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 29 return q*x; 30 } 31 32 namespace brute{ 33 34 struct edge{ int nt,to; }g[22]; 35 36 int head[12],vi[12],vis[22],top,num; 37 ll st[2000010]; 38 39 il void insert(RG int from,RG int to){ 40 g[++num]=(edge){head[from],to},head[from]=num; return; 41 } 42 43 il int find(RG int x,RG int T){ 44 if (x==T) return 1; vi[x]=1; RG int v; 45 for (RG int i=head[x];i;i=g[i].nt){ 46 v=g[i].to; if (vi[v]) continue; 47 if (find(v,T)) return 1; 48 } 49 return 0; 50 } 51 52 il int check(){ 53 memset(head,0,sizeof(head)),num=0; 54 for (RG int i=1;i<=m;++i) 55 if (!vis[i]) insert(G[i].u,G[i].v); 56 memset(vi,0,sizeof(vi)); return !find(S,T); 57 } 58 59 il void dfs(RG int x,RG ll tot){ 60 if (x>m){ 61 if (check()) st[++top]=tot; 62 return; 63 } 64 vis[x]=1,dfs(x+1,tot+G[x].w); 65 vis[x]=0,dfs(x+1,tot); return; 66 } 67 68 int main(){ 69 dfs(1,0),sort(st+1,st+top+1); 70 for (RG int i=1;i<=top && i<=k;++i) printf("%lld\n",st[i]); 71 if (top<k) puts("-1"); return 0; 72 } 73 74 } 75 76 namespace heap{ 77 78 struct data{ 79 ll val; int i,level; 80 il bool operator < (const data &a) const{ return val>a.val; } 81 }; 82 83 struct node{ ll a,b; }e[200010]; 84 85 priority_queue <data> Q; 86 87 ll mincut; 88 89 il int cmp(const node &x,const node &y){ 90 if (x.a==y.a) return x.b<y.b; return x.a<y.a; 91 } 92 93 int main(){ 94 for (RG int i=1,x;i<=m;++i){ 95 x=G[i].u; if (x==S || x==T) x=G[i].v; 96 if (!e[x].a) e[x].a=G[i].w; else{ 97 e[x].b=G[i].w; 98 if (e[x].a<e[x].b) swap(e[x].a,e[x].b); 99 mincut+=e[x].b,e[x].a-=e[x].b;100 }101 }102 if (T==n) e[S]=e[n-1],e[T]=e[n]; else e[S]=e[n],e[T]=e[n-1];103 n-=2,--k,sort(e+1,e+n+1,cmp),printf("%lld\n",mincut);104 Q.push((data){mincut+e[1].a,1,1});105 for (;k && !Q.empty();--k){106 RG data x=Q.top(),tmp; Q.pop();107 printf("%lld\n",x.val);108 if (x.level<2){109 tmp.val=x.val+e[x.i].b;110 tmp.i=x.i,tmp.level=x.level+1,Q.push(tmp);111 }112 if (x.i<n && x.level==1){113 tmp.val=x.val-e[x.i].a+e[x.i+1].a;114 tmp.i=x.i+1,tmp.level=1,Q.push(tmp);115 }116 if(x.i<n){117 tmp.val=x.val+e[x.i+1].a;118 tmp.i=x.i+1,tmp.level=1,Q.push(tmp);119 }120 }121 if (k) puts("-1"); return 0;122 }123 124 }125 126 namespace kthcut{127 128 #define M (3005)129 #define N (60)130 131 int head[N],cur[N],havs[N],havt[N],ds[N],dt[N],d[N],vis[N],in[M],q[10*M],num=1;132 133 struct Graph{134 135 struct edge{ int nt,to,flow,cap; }g[M];136 137 il void insert(RG int from,RG int to,RG int cap){138 g[++num]=(edge){head[from],to,0,cap},head[from]=num; return;139 }140 141 il int bfs(RG int S,RG int T){142 memset(d,0,sizeof(d)),d[S]=1;143 RG int h=0,t=1; q[t]=S;144 while (h<t){145 RG int x=q[++h],v;146 for (RG int i=head[x];i;i=g[i].nt){147 v=g[i].to;148 if (!d[v] && g[i].cap>g[i].flow){149 d[v]=d[x]+1,q[++t]=v;150 if (v==T) return 1;151 }152 }153 }154 return d[T];155 }156 157 il ll dfs(RG int x,RG int T,RG int a){158 if (!a || x==T) return a; RG ll flow=0,f;159 for (RG int &i=cur[x],v;i;i=g[i].nt){160 v=g[i].to;161 if (d[v]==d[x]+1 && g[i].cap>g[i].flow){162 f=dfs(v,T,min(a,g[i].cap-g[i].flow));163 if (!f){ d[v]=0; continue; }164 g[i].flow+=f,g[i^1].flow-=f;165 flow+=f,a-=f; if (!a) return flow;166 }167 }168 return flow;169 }170 171 il ll mincut(RG int S,RG int T){172 RG ll cut=0;173 while (bfs(S,T)){174 memcpy(cur,head,sizeof(head));175 cut+=dfs(S,T,inf); if (cut>inf) return cut;176 }177 return cut;178 }179 180 il void DFS(RG int x){181 vis[x]=1;182 for (RG int i=head[x];i;i=g[i].nt)183 if (g[i].cap>g[i].flow && !vis[g[i].to]) DFS(g[i].to);184 return;185 }186 187 il void getcut(){188 memset(vis,0,sizeof(vis)),memset(in,0,sizeof(in)),DFS(S);189 for (RG int i=1;i<=m;++i) if (vis[G[i].u] && !vis[G[i].v]) in[i]=1;190 return;191 }192 193 }Gra,lin1,lin2;194 195 struct node{196 197 int must[M],stop[M],id,ww; ll val;198 199 il bool operator < (const node &a) const{ return val>a.val; }200 201 il void build(){202 val=0,lin1=Gra;203 for (RG int i=1;i<=m;++i)204 if (must[i]) val+=G[i].w,lin1.g[i<<1].cap=0;205 else if (stop[i]) lin1.g[i<<1].cap=inf;206 val+=lin1.mincut(S,T),lin1.getcut(),ww=inf,id=0;207 memset(havs,0,sizeof(havs)),memset(havt,0,sizeof(havt));208 for (RG int i=1;i<=m;++i){209 if (must[i] || stop[i]) continue;210 if (in[i]){211 if (!havs[G[i].u]){212 havs[G[i].u]=1,lin2=lin1;213 ds[G[i].u]=lin2.mincut(S,G[i].u);214 }215 if (!havt[G[i].v]){216 havt[G[i].v]=1,lin2=lin1;217 dt[G[i].v]=lin2.mincut(G[i].v,T);218 }219 if (ds[G[i].u]<ww) ww=ds[G[i].u],id=i;220 if (dt[G[i].v]<ww) ww=dt[G[i].v],id=i;221 } else if (G[i].w<ww) ww=G[i].w,id=i;222 }223 val+=ww; return;224 }225 226 }a,b;227 228 priority_queue <node> Q;229 230 int main(){231 for (RG int i=1;i<=m;++i){232 Gra.insert(G[i].u,G[i].v,G[i].w);233 Gra.insert(G[i].v,G[i].u,0);234 }235 --k,lin1=Gra,printf("%lld\n",lin1.mincut(S,T));236 a.build(); if (a.val<inf) Q.push(a);237 for (;k && !Q.empty();--k){238 a=b=Q.top(),Q.pop(),printf("%lld\n",a.val);239 a.must[a.id]=1,a.build(); if (a.val<inf) Q.push(a);240 b.stop[b.id]=1,b.build(); if (b.val<inf) Q.push(b);241 }242 if (k) puts("-1"); return 0;243 }244 245 }246 247 int main(){248 #ifndef ONLINE_JUDGE249 freopen("kthcut.in","r",stdin);250 freopen("kthcut.out","w",stdout);251 #endif252 n=gi(),m=gi(),S=gi(),T=gi(),k=gi();253 for (RG int i=1;i<=m;++i)254 G[i].u=gi(),G[i].v=gi(),G[i].w=gi(),mx=max(mx,G[i].w);255 if (m<=20) brute::main();256 else if (n<=50 && k<=100 && mx<=65536) kthcut::main();257 else heap::main();258 return 0;259 }
bzoj3882 [Wc2015]K小割
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。