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;
}