[BZOJ2400]Spoj 839 Optimal Marks（最小割）

2019-11-08 02:09:58

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

首先考虑如何求出第一问要求边权和最小按位分开考虑，实际上就是让这一位上的1尽量少对于每一个点i，如果这一位已经确定，那么0:s->i,inf，1:i->t,inf 对于每一条边，将两个端点x,y，x->y,1；y->x,1 这样跑最小割

据说这样跑完最小割了之后加一个限流然后跑费用流是可以的不过有一个非常巧妙的方法能将这两问的答案一起求出来同样按位分开考虑，同样是想要1尽量少对于每一个点i，如果这一位已经确定，那么0:s->t,inf，1:i->t,inf；如果这一位没有确定，那么s->i,1 对于每一条边，将两个端点x,y，x->y,n+1；y->x,n+1 这样跑出来最小割，令x=ans/(n+1)，y=ans%(n+1) 可以发现x即为第一位的答案，也就是边权和最少个数的1 y的含义即为点权和最少个数的1

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<queue>using namespace std;#define LL long long#define N 510#define E 10005#define inf 2000000000int n,m,x,y,Max,s,t,maxflow,cnte,cntv;int val[N],e[N][N];int tot,point[N],nxt[E],v[E],remain[E];int deep[N],cur[N],last[N],num[N];queue <int> q;LL sume,sumv;void addedge(int x,int y,int cap){// PRintf("%d %d %d/n",x,y,cap); ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0;}void bfs(int t){ for (int i=1;i<=t;++i) deep[i]=t; deep[t]=0; for (int i=1;i<=t;++i) cur[i]=point[i]; while (!q.empty()) q.pop(); q.push(t); while (!q.empty()) { int now=q.front();q.pop(); for (int i=point[now];i!=-1;i=nxt[i]) if (deep[v[i]]==t&&remain[i^1]) { deep[v[i]]=deep[now]+1; q.push(v[i]); } }}int addflow(int s,int t){ int now=t,ans=inf; while (now!=s) { ans=min(ans,remain[last[now]]); now=v[last[now]^1]; } now=t; while (now!=s) { remain[last[now]]-=ans; remain[last[now]^1]+=ans; now=v[last[now]^1]; } return ans;}void isap(int s,int t){ bfs(t); for (int i=1;i<=t;++i) ++num[deep[i]]; int now=s; while (deep[s]<t) { if (now==t) { maxflow+=addflow(s,t); now=s; } bool has_find=0; for (int i=cur[now];i!=-1;i=nxt[i]) if (deep[v[i]]+1==deep[now]&&remain[i]) { has_find=1; cur[now]=i; last[v[i]]=i; now=v[i]; break; } if (!has_find) { int minn=t-1; for (int i=point[now];i!=-1;i=nxt[i]) if (remain[i]) minn=min(minn,deep[v[i]]); if (!(--num[deep[now]])) break; ++num[deep[now]=minn+1]; cur[now]=point[now]; if (now!=s) now=v[last[now]^1]; } }}int main(){ scanf("%d%d",&n,&m); s=n+1,t=s+1; for (int i=1;i<=n;++i) { scanf("%d",&val[i]); if (val[i]>=0) sumv+=val[i]; } for (int i=1;i<=m;++i) { scanf("%d%d",&x,&y); ++e[x][y],++e[y][x]; } for (int bit=29;bit>=0;--bit) { tot=-1;memset(point,-1,sizeof(point)); memset(num,0,sizeof(num)); for (int i=1;i<=n;++i) if (val[i]<0) addedge(s,i,1); else { x=(val[i]>>bit)&1; if (x) addedge(i,t,inf); else addedge(s,i,inf); } for (int i=1;i<=n;++i) for (int j=i+1;j<=n;++j) for (int k=1;k<=e[i][j];++k) { addedge(i,j,n+1); addedge(j,i,n+1); } maxflow=0;isap(s,t); cnte=maxflow/(n+1); cntv=maxflow%(n+1); sume+=(LL)(1<<bit)*(LL)cnte; sumv+=(LL)(1<<bit)*(LL)cntv; } printf("%lld/n",sume); printf("%lld/n",sumv);}