最近比较懒~ 详见这里 考虑每位分开 把01转化为ST集 变成最小割 然后我们还要解决点权尽量小的问题 有两种方法
一是从T开始bfs出T集二是设立二维权值 边权是第一优先级 点权是第二优先级 详情百度 #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define cl(x) memset(x,0,sizeof(x)) using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=505; const int M=20005; struct edge{ int u,v,f,next; }G[M]; int head[N],inum=1; inline void add(int u,int v,int f,int p){ G[p].u=u; G[p].v=v; G[p].f=f; G[p].next=head[u]; head[u]=p; } inline void link(int u,int v,int f){ add(u,v,f,++inum); add(v,u,0,++inum); } #define V G[p].v int S,T; int dis[N]; int Q[N],l,r; inline bool bfs(){ for (int i=1;i<=T;i++) dis[i]=-1; l=r=-1; Q[++r]=S; dis[S]=0; while (l<r){ int u=Q[++l]; for (int p=head[u];p;p=G[p].next) if (G[p].f && dis[V]==-1){ dis[V]=dis[u]+1; Q[++r]=V; if (V==T) return 1; } } return 0; } int cur[N]; inline int dfs(int u,int flow){ if (u==T) return flow; int used=0; for (int p=head[u];p;p=G[p].next) if (G[p].f && dis[V]==dis[u]+1){ int d=dfs(V,min(flow-used,G[p].f)); G[p].f-=d; G[p^1].f+=d; used+=d; if (used==flow) break; } if (!used) dis[u]=-1; return used; } inline int Dinic(){ int ans=0; while (bfs()) memcpy(cur,head,sizeof(cur)),ans+=dfs(S,1<<30); return ans; } int n,m,val[N]; int u[M],v[M]; int main(){ ll ans1=0,ans2=0,ans; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(m); for (int i=1;i<=n;i++) read(val[i]); for (int i=1;i<=m;i++) read(u[i]),read(v[i]); for (int k=30;~k;k--){ S=n+1,T=n+2; for (int i=1;i<=n;i++) if (val[i]>=0) val[i]>>k&1?link(i,T,1<<30):link(S,i,1<<30); for (int i=1;i<=m;i++) link(u[i],v[i],10000),link(v[i],u[i],10000); for (int i=1;i<=n;i++) link(S,i,1); ans=Dinic(); ans1+=ans/10000*(1<<k); ans2+=ans%10000*(1<<k); cl(head); inum=1; } printf("%lld\n%lld\n",ans1,ans2); return 0; }