SPOJ OPTM Optimal Marks（构图+最小割）

OPTM - Optimal Marks

no tags 

You are given an undirected graph G(V, E). Each vertex has a mark which is an integer from the range [0..231 – 1]. Different vertexes may have the same mark.

For an edge (u, v), we define Cost(u, v) = mark[u] xor mark[v].

Now we know the marks of some certain nodes. You have to determine the marks of other nodes so that the total cost of edges is as small as possible.

Input

T (1 ≤ T

N and M (0 < N <= 500, 0 <= M <= 3000). N is the number of vertexes and M is the number of edges. Then M

K, representing the number of nodes whose mark is known. The next K

Output

N lines integer the output. The Kth line contains an integer number representing the mark of node K. If there are several solutions, you have to output the one which minimize the sum of marks. If there are several solutions, just output any of them.

Example

Input:
1
3 2
1 2
2 3
2
1 5
3 100

Output:      

      大致题意：给你一个图，有一些点初始已经有了标号。图中的边权定义为连接的两个点的点权异或值，现在问你如何给未标号的点编号，使得标号之后图的权值和最小。

        论文原题。由于是异或，而异或操作与二进制的每一位有关，不同二进制位之间是没有影响的。所以我们可以考虑对每一个二进制位单独处理。如果单独处理，我们可以发现，所有点在这一个二进制位的编号，要么是0要么是1。而显然，我们的目标是把这些个点分成两个部分，然后使得0与1相连的边尽可能的少。很自然的，我们可以想到最小割的模型。

        首先，既然分为两部分，那么一边是0，另一边就表示1。源点s 连接所有已知编号且当前位为0 的点，流量为无穷大。所有已知编号且当前点编号为1的点连接汇点，流量为无穷大。然后，其他的未知编号的点按照原图对应在新图上连接，流量为1。构建好图之后，根据割的性质，割两边的点被分为两个部分，左边为0右边为1，两部分内部异或和为0，代价恰好就是割集中的流量和。于是这个网络的一个最小割就恰好对应这个标号问题的最优解。

        关于最后的方案，每一次网络流完毕之后，我们从源点开始跑一遍，走所有流量大于0的边，能够走到的点都属于左边/值为0的集合，否则属于右边/值为1的集合，对应增加数值即可。具体见代码：

#include<bits/stdc++.h>
#define LL long long
#define INF 0x3f
#define M 10010
using namespace std;

vector<int> g[M];
int ans[M],num[M];
bool v[M];

namespace ISAP
{
    int H[M],d[M],cur[M],pre[M],gap[M],Q[M],RC[M];
    struct Edge{int u,v,c,n;} E[M];
    int nv,flow,head,tail,cntE,f;

    void init(){cntE=0; memset(H,-1,sizeof(H));}

    void addedge(int u,int v,int c)
    {
        E[cntE]=Edge{u,v,c,H[u]}; H[u]=cntE++;
        E[cntE]=Edge{v,u,0,H[v]}; H[v]=cntE++;
    }

    void revbfs(int s,int t)
    {
        head=tail=0 ;
        memset(d,-1,sizeof(d));
        memset(gap,0,sizeof(gap));
        Q[tail++]=t;d[t]=0;gap[d[t]]=1;
        while (head!=tail)
        {
            int u=Q[head++];
            for (int i=H[u];~i;i=E[i].n)
            {
                int v=E[i].v; if (~d[v]) continue;
                d[v]=d[u]+1; gap[d[v]]++; Q[tail++]=v;
            }
        }
    }

    int isap(int s,int t)
    {
        memcpy(cur,H,sizeof(cur)); nv=t;
        flow=0; revbfs(s,t); int u=pre[s]=s,i;
        while (d[s]<nv)
        {
            if (u==t)
            {
                f=INF;
                for (i=s;i!=t;i=E[cur[i]].v)
                    if (f>E[cur[i]].c) f=E[cur[i]].c,u=i;
                flow += f;
                for (i=s;i!=t;i=E[cur[i]].v)
                    E[cur[i]].c-=f,E[cur[i]^1].c+=f;
            }
            for (i=cur[u];~i;i=E[i].n)
                if (E[i].c&&d[u]==d[E[i].v]+1) break ;
            if (~i) cur[u]=i,pre[E[i].v]=u,u=E[i].v;
            else
            {
                if (0==--gap[d[u]]) break ;
                int minv=nv,v;
                for (int i=H[u];~i;i=E[i].n)
                {
                    v=E[i].v;
                    if (E[i].c&&minv>d[v]) minv=d[v],cur[u]=i;
                }
                d[u]=minv+1; gap[d[u]]++; u=pre[u];
            }
        }
        return flow ;
    }

    void dfs(int x)
    {
        v[x]=1;
        for(int i=H[x];~i;i=E[i].n)
        {
            int to=E[i].v;
            if (E[i].c<=0||v[to]) continue;
            dfs(to);
        }
    }
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(g,0,sizeof(g));
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int k;
        scanf("%d",&k);
        for(int i=1;i<=k;i++)
        {
            int y;
            scanf("%d%d",&num[i],&y);
            ans[num[i]]=y;
        }
        int s=n+1,t=n+2;
        for(int i=0;i<32;i++)
        {
            ISAP::init();
            using namespace ISAP;
            for(int j=1;j<=k;j++)
            {
                if (ans[num[j]])
                {
                    if (ans[num[j]]&(1<<i)) addedge(s,num[j],INF);
                                        else addedge(num[j],t,INF);
                }
            }
            for(int j=1;j<=n;j++)
            {
                for(int p=0;p<g[j].size();p++) addedge(j,g[j][p],1);
            }
            memset(v,0,sizeof(v));
            isap(s,t);
            dfs(s);
            for(int j=1;j<=n;j++) ans[j]|=v[j]<<i;
        }
        for(int i=1;i<=n;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}