[SPOJ839]OPTM-Optimal Marks

佚名 6年前 (2019-04-26) 随笔 1804人围观抢沙发百度已收录

题意

给你一个无向图G（V，E）。每个顶点都有一个int范围内的整数的标记。不同的顶点可能有相同的标记。
对于边（u，v），我们定义Cost（u，v）= mark [u] xor mark [v]。
现在我们知道某些节点的标记了。你需要确定其他节点的标记，以使边的总成本尽可能小。

题解

最小割
发现贡献是异或的形式
所以考虑每一位单独处理
对于第\(w\)位
考虑将原图划分成两个集合
一个集合是\(S\)集,另外一个集合是\(T\)集
\(S\)集代表这个点这一位是\(1\)
\(T\)集代表这个点这一位是\(0\)
然后将原图中的边连双向边,流量为\(1\)
如果一个点\(u\)的点权已经确定,那么如果这一位为\(1\)就连\(S\to u\),流量为\(INF\),如果这一位为\(0\)就连\(u\to T\),流量为\(INF\)
最后所有在\(S\)集(即\(bfs\)可达的点)这一位都是\(1\)

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 605 ;
const int N = 5005 ;
const int INF = 1e9 ;
using namespace std ;

inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
    return x*w ;
}

bool vis[M] ;
int n , m , S , T , K , num = 1 ;
int fr[N] , tw[N] , val[M] , hea[M] , ans[M] , dep[M] ;

struct E { int nxt , to , dis ; } edge[N * 5] ;

inline void Bclear() {
    memset(vis , false , sizeof(vis)) ;
    memset(ans , 0 , sizeof(ans)) ;
}
inline void Clear() {
    num = 1 ; 
    memset(hea , 0 , sizeof(hea)) ;
}
inline void Insert_edge(int from , int to , int dis) {
    edge[++num].nxt = hea[from] ;
    edge[num].to = to ;
    edge[num].dis = dis ;
    hea[from] = num ;
}
inline void add_edge(int u , int v , int w) {
    Insert_edge(u , v , w) ;
    Insert_edge(v , u , 0) ;
}
inline bool bfs() {
    queue < int > q ; q.push(S) ;
    memset(dep , 0 , sizeof(dep)) ; dep[S] = 1 ;
    while(!q.empty()) {
        int u = q.front() ; q.pop() ;
        for(int i = hea[u] ; i ; i = edge[i].nxt) {
            int v = edge[i].to ;
            if(!dep[v] && edge[i].dis) {
                dep[v] = dep[u] + 1 ;
                q.push(v) ;
            }
        }
    }
    return dep[T] ;
}
int dfs(int u , int dis) {
    if(u == T || !dis) return dis ; int sum = 0 ;
    for(int i = hea[u] ; i ; i = edge[i].nxt) {
        int v = edge[i].to ;
        if(dep[v] == dep[u] + 1 && edge[i].dis > 0) {
            int diss = dfs(v , min(dis , edge[i].dis)) ;
            if(diss > 0) {
                edge[i].dis -= diss ; edge[i ^ 1].dis += diss ;
                sum += diss ; dis -= diss ; if(!dis) break ;
            }
        }
    }
    if(!sum) dep[u] = -1 ; return sum ;
}
inline void dinic() {
    while(bfs())
        dfs(S , INF) ;
}
int main() {
    int Case = read() ;
    while(Case --) {
        Bclear() ;
        n = read() ; m = read() ;
        for(int i = 1 ; i <= m ; i ++) 
            fr[i] = read() , tw[i] = read() ;
        K = read() ;
        for(int i = 1 , x ; i <= K ; i ++) {
            x = read() ;
            val[x] = read() ;
            vis[x] = true ;
        }
        S = 0 ; T = n + 1 ;
        for(int w = 0 ; w < 31 ; w ++) {
            Clear() ;
            for(int i = 1 , u , v ; i <= m ; i ++) {
                u = fr[i] , v = tw[i] ;
                add_edge(u , v , 1) ;
                add_edge(v , u , 1) ;
            }
            for(int i = 1 ; i <= n ; i ++) {
                if(!vis[i]) continue ;
                if(val[i] & (1 << w))
                    add_edge(S , i , INF) ;
                else add_edge(i , T , INF) ;
            }
            dinic() ;
            bfs() ;
            for(int i = 1 ; i <= n ; i ++)
                if(dep[i])
                    ans[i] |= (1 << w) ;
        }
        for(int i = 1 ; i <= n ; i ++)
            printf("%d\n",ans[i]) ;
    }
    return 0 ;
}