Optimal Marks(optimal)

题目描述

定义无向图边的值为这条边连接的两个点的点权异或值。

定义无向图的值为无向图中所有边的值的和。

给定nn个点mm条边构成的图。其中有些点的权值是给定的，另外一些由你来定。点权必须为非负数。现在你需要使无向图的值最小，且在保证图的权值最小的情况下点的权值的和最小。

输入

第一行两个数nn和mm，表示图的点数和边数。

接下来nn行，每行一个数，表示每个点的权值。如果是负数，表示该点点权由你定，点权绝对值不超过109109。

接下来mm行，每行两个数aa和bb，表示aa和bb之间有无向边相连。（保证无重边和自环，但不保证是连通图）。

输出

第一行，一个数，表示无向图的最小值。

第二行，一个数，表示此时无向图中点权的和的值。

样例输入

样例输出

2

2

提示

对于所有数据：

n≤500n≤500 m≤2000m≤2000

样例解释：

将22号点权值定位00即可。

solution

考虑拆位，这样权值就变成了0/1

建图

若w[i]=1

lj(S,i,inf);

若w[i]=0

lj(i,T,inf);

对于原图中的边（u,v）

lj(u,v,1);lj(v,u,1);

然后就是最小割的问题了

割在S表示选1，T表示选0

这样就解决了第一问。

对于第二问，我们要求T集尽量大

由于流量只有0和1，我们可以从S开始遍历，发现0就返回，找出最小的S集

e[i].v打成k调了一下午。。。

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define maxn 5005

#define inf 1e9

using namespace std;

int n,m,w[maxn],a1[20002],b1[20002],tot=1,head[maxn],S,T;

int d[maxn],flag[maxn],cur[maxn],ans,fl[maxn];

long long anse,ansv;

struct node{

    int v,nex,cap;

}e[100005];

void Q(){

    tot=1;

    memset(head,0,sizeof head);

}

void lj(int t1,int t2,int t3){

    tot++;e[tot].v=t2,e[tot].cap=t3;e[tot].nex=head[t1];head[t1]=tot;

}

bool BFS(){

    for(int i=1;i<=T;i++)d[i]=inf,flag[i]=0;

    queue<int>q;q.push(S);d[S]=0;

    while(!q.empty()){

        int x=q.front();q.pop();cur[x]=head[x];

        for(int i=head[x];i;i=e[i].nex){

            if(d[e[i].v]>d[x]+1&&e[i].cap){

                d[e[i].v]=d[x]+1;

                if(!flag[e[i].v]){

                    flag[e[i].v]=1;q.push(e[i].v);

                }

            }

        }

        flag[x]=0;

    }

    return d[T]!=inf;

}

int lian(int k,int a){

    //cout<<k<<' '<<a<<endl;

    if(k==T||!a)return a;

    int f,flow=0;

    for(int& i=cur[k];i;i=e[i].nex){

        if(d[e[i].v]==d[k]+1&&(f=lian(e[i].v,min(a,e[i].cap)))>0){

            flow+=f;a-=f;

            e[i].cap-=f;e[i^1].cap+=f;

            if(!a)break;

        }

    }

    return flow;

}

void dfs(int k,int fa,int num){

    if(w[k]<0){ansv+=(1<<num);}fl[k]=1;

    for(int i=head[k];i;i=e[i].nex){

        if(e[i].v!=fa){

            if(e[i].cap>0&&!fl[e[i].v])dfs(e[i].v,k,num);

        }

    }

}

int main()

{

    cin>>n>>m;S=n+1,T=S+1;

    for(int i=1;i<=n;i++){scanf("%d",&w[i]);if(w[i]>0)ansv+=w[i];}

    for(int i=1;i<=m;i++)scanf("%d%d",&a1[i],&b1[i]);

    for(int ws=30;ws>=0;ws--){

        Q();

        for(int i=1;i<=n;i++){

            if(w[i]<0)continue;

            if((w[i]&(1<<ws))>0)lj(S,i,inf),lj(i,S,0);

            else lj(i,T,inf),lj(T,i,0);

        }

        for(int i=1;i<=m;i++){

            lj(a1[i],b1[i],1),lj(b1[i],a1[i],0);

            lj(a1[i],b1[i],0),lj(b1[i],a1[i],1);

        }

        ans=0;

        while(BFS())ans+=lian(S,inf);

        //cout<<ans<<endl;

        anse+=1LL*ans*(1<<ws);

        memset(fl,0,sizeof fl);

        dfs(S,0,ws);

    }

    printf("%lld\n%lld\n",anse,ansv);

    return 0;

}

LJ