SPOJ-OPTM OPTIMAL MARKS(按位建图 最小割)

【标题含义】给定一个无向图，每个点都有一个标签mark[i]，不同的点可能有相同的标签。对于边 (u, v)，其权重定义为 mark[u] xor mark[v]。现在已经确定了一些点的标签，请确定剩余点的标签，以使边缘权重的总和最小化。 (0 < N <= 500, 0 <= M <= 3000, 0 <= mark[i] <= 2^31-1) 以胡波涛《最小割模型在信息学竞赛中的应用》为例。非常好的问题！非常推荐！ [想法] 我们将问题数学公式化为： Minimum sigma(we) = sigma (u, v)∈E ( mark(u) xor mark(v) ) 对于 XOR 问题，我们发现每个binary 位互不影响，所以我们可以一一做这种题。那么我们的公式可以进一步转化为： Minimum sigma (u, v)∈E { sigma i=0~oo(2^i) ? sigma(mark(u, i) xor mark(v, i)) } 在这个方式，我们加强mark的限制：它只能是0或1。也就是说，分数将分为两类。再看一遍，我们发现只有当u和v不同时，xor运算的结果才为1，即这样一条有效边的两端必然属于不同的点集。这是什么样的？不只是尖端吗？ ~而问题恰好是最小要求，所以将问题转化为最小割~（注意培养这种问题转化和模型发现的能力！） 那么具体的最小割网络GN模型：构建一个源点并将其发送到每个标记为 1 的点连接到 oo 流的一条边（我们将解释为什么源点连接到标记为 1 的点）；建立一个接收器，并将oo流的边缘连接到标记为0的每个点；将原始图像中的边缘容量设置为 1 以加入 GN。得到的最小割是二进制位下标号xor之和最小的情况。但是标题也要求输出所有点的标签，标签的总和也是最小的。那么如何保证标签之和最小呢？无非就是尽可能取0。那么该怎么办？首先我们看一下如何标注那些未标注的点：很容易认为最小割把网络分成了两个点集，那么显然每个点标注应该和所在点集中的标注点相同，所以我当然希望标签是0。多拿点分数。然后注意我们从源点开始划分点集开始dfs，那么这样绘制的最小割边集显然更偏向源点，也就是这样划分的S个集点最少。所以源点当然是连接到标签为1的点~【代码】

#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXV = 505;
const int MAXE = 10005;
const int oo = 0x3fffffff;

/* Dinic-2.0-2013.07.21: adds template.  double & int 转换方便多了，也不易出错 ~*/
template
struct Dinic{
    struct node{
        int u, v;
        T flow;
        int opp;
        int next;
    }arc[2*MAXE];
    int vn, en, head[MAXV];
    int cur[MAXV];
    int q[MAXV];
    int path[2*MAXE], top;
    int dep[MAXV];
    void init(int n){
        vn = n;
        en = 0;
        mem(head, -1);
    }
    void insert_flow(int u, int v, T flow){
        arc[en].u = u;
        arc[en].v = v;
        arc[en].flow = flow;
        arc[en].next = head[u];
        head[u] = en ++;

        arc[en].u = v;
        arc[en].v = u;
        arc[en].flow = 0;
        arc[en].next = head[v];
        head[v] = en ++;
    }
    bool bfs(int s, int t){
        mem(dep, -1);
        int lq = 0, rq = 1;
        dep[s] = 0;
        q[lq] = s;
        while(lq < rq){
            int u = q[lq ++];
            if (u == t){
                return true;
            }
            for (int i = head[u]; i != -1; i = arc[i].next){
                int v = arc[i].v;
                if (dep[v] == -1 && arc[i].flow > 0){
                    dep[v] = dep[u] + 1;
                    q[rq ++] = v;
                }
            }
        }
        return false;
    }
    T solve(int s, int t){
        T maxflow = 0;
        while(bfs(s, t)){
            int i, j;
            for (i = 1; i <= vn; i ++)  cur[i] = head[i];
            for (i = s, top = 0;;){
                if (i == t){
                    int mink;
                    T minflow = 0x3fffffff;
                    for (int k = 0; k < top; k ++)
                        if (minflow > arc[path[k]].flow){
                            minflow = arc[path[k]].flow;
                            mink = k;
                        }
                    for (int k = 0; k < top; k ++)
                        arc[path[k]].flow -= minflow, arc[path[k]^1].flow += minflow;
                    maxflow += minflow;
                    top = mink;
                    i = arc[path[top]].u;
                }
                for (j = cur[i]; j != -1; cur[i] = j = arc[j].next){
                    int v = arc[j].v;
                    if (arc[j].flow && dep[v] == dep[i] + 1)
                        break;
                }
                if (j != -1){
                    path[top ++] = j;
                    i = arc[j].v;
                }
                else{
                    if (top == 0)   break;
                    dep[i] = -1;
                    i = arc[path[-- top]].u;
                }
            }
        }
        return maxflow;
    }
};
Dinic  dinic;
int mark[MAXV];
bool if_mark[MAXV];
struct path{
    int u, v;
}p[MAXE];
bool vis[MAXV];
int st[MAXV];   //ST集
void dfs(int u){
    vis[u] = 1;
    st[u] = 1;
    for (int i = dinic.head[u]; i != -1; i = dinic.arc[i].next){
        if (dinic.arc[i].flow <= 0) continue;
        int v = dinic.arc[i].v;
        if (!vis[v]){
            dfs(v);
        }
    }
    return ;
}
int main(){
        int t;
        scanf("%d", &t);
        while(t --){
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= m; i ++){
            scanf("%d %d", &p[i].u, &p[i].v);
        }
        int k;
        mem(mark, 0);
        mem(if_mark, false);
        scanf("%d", &k);
        int maxn = 0;
        for (int i = 0; i < k; i ++){
            int u;
            scanf("%d", &u);
            scanf("%d", &mark[u]);
            maxn = max(maxn, mark[u]);
            if_mark[u] = true;
        }
        int oi = ceil(log(maxn)/log(2));
        for (int k = 0; k < oi; k ++){
            dinic.init(n+2);
            for (int i = 1; i <= n; i ++){
                if (!if_mark[i])
                    continue;
                if ((mark[i] & (1 << k))){
                    dinic.insert_flow(n+1, i, oo);
                }
                else{
                    dinic.insert_flow(i, n+2, oo);
                }
            }
            for (int i = 1; i <= m; i ++){
                dinic.insert_flow(p[i].u, p[i].v, 1);
                dinic.insert_flow(p[i].v, p[i].u, 1);
            }
            dinic.solve(n+1, n+2);
            mem(st, 0);
            mem(vis, 0);
            dfs(n+1);       //残留网络中dfs确定点S、T集
            for (int i = 1; i <= n; i ++){
                if (st[i] == 1 && !if_mark[i]){
                    mark[i] += (1 << k);
                }
            }
        }
        for (int i = 1; i <= n; i ++){
            printf("%d\n", mark[i]);
        }
        }
        return 0;
}

([Title Meaning] given an undirected graph, each point has a label mark [i], and different points may have the same label. For edges (U, V), the weight is defined as mark [u] XOR mark [v]. Now that the labels of some points have been determined, please determine the labels of the remaining points to minimize the sum of edge weights. (0 < n < = 500, 0 < = m < = 3000, 0 < = mark [i] < = 2 ^ 31-1) take Hu Botao's application of minimum cut model in informatics competition as an example. Very good question! Highly recommended! [idea] we formulated the problem mathematically as: minimum sigma (we) = sigma (U, V) ∈ e (mark (U) XOR mark (V)). For XOR problem, we found that each binary bit does not affect each other, so we can do this problem one by one. Then our formula can be further transformed into: minimum sigma (U, V) ∈ e {sigma I = 0 ~ OO (2 ^ I)? Sigma (mark (U, I) XOR mark (V, I))}. In this way, we strengthen the limitation of mark: it can only be 0 or 1. In other words, scores will be divided into two categories. Again, we find that only when u and V are different, the result of XOR operation is 1, that is, the two ends of such an effective edge must belong to different point sets. What's this like? Not just the tip~ The problem is just the minimum requirement, so turn the problem into the minimum cut ~ (pay attention to cultivate the ability of problem transformation and Model Discovery!) Then the specific minimum cut network GN model: build a source point and send it to each point marked 1 and connect it to an edge of the OO stream (we will explain why the source point is connected to the point marked 1); Establish a receiver and connect the edge of the OO stream to each point marked 0; Set the edge capacity in the original image to 1 to add GN. The minimum cut obtained is the case where the sum of the labels XOR under the binary bits is the smallest. However, the title also requires the output of labels of all points, and the sum of labels is also the smallest. So how to minimize the sum of labels? Nothing more than taking 0 as much as possible. So what should I do? First, let's take a look at how to label those unmarked points: it's easy to think that the minimum cut divides the network into two point sets. Obviously, the label of each point should be the same as the label points in the point set, so I certainly want the label to be 0. Get more points. Then note that we divide the point set from the source point and start DFS, so the minimum cut edge set drawn in this way is obviously more inclined to the source point, that is, the s set points divided in this way are the least. So the source point is of course connected to the point labeled 1 ~ [Code]
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXV = 505;
const int MAXE = 10005;
const int oo = 0x3fffffff;
/* Dinic-2.0-2013.07.21: adds template.   Double & int conversion is much more convenient and error free~*/
template
struct Dinic{
struct node{
int u, v;
T flow;
int opp;
int next;
}arc[2*MAXE];
int vn, en, head[MAXV];
int cur[MAXV];
int q[MAXV];
int path[2*MAXE], top;
int dep[MAXV];
void init(int n){
vn = n;
en = 0;
mem(head, -1);
}
void insert_ flow(int u, int v, T flow){
arc[en]. u = u;
arc[en]. v = v;
arc[en]. flow = flow;
arc[en]. next = head[u];
head[u] = en ++;
arc[en]. u = v;
arc[en]. v = u;
arc[en]. flow = 0;
arc[en]. next = head[v];
head[v] = en ++;
}
bool bfs(int s, int t){
mem(dep, -1);
int lq = 0, rq = 1;
dep[s] = 0;
q[lq] = s;
while(lq < rq){
int u = q[lq ++];
if (u == t){
return true;
}
for (int i = head[u]; i != -1; i = arc[i].next){
int v = arc[i]. v;
if (dep[v] == -1 && arc[i].flow > 0){
dep[v] = dep[u] + 1;
q[rq ++] = v;
}
}
}
return false;
}
T solve(int s, int t){
T maxflow = 0;
while(bfs(s, t)){
int i, j;
for (i = 1; i <= vn; i ++)  cur[i] = head[i];
for (i = s, top = 0;;) {
if (i == t){
int mink;
T minflow = 0x3fffffff;
for (int k = 0; k < top; k ++)
if (minflow > arc[path[k]].flow){
minflow = arc[path[k]]. flow;
mink = k;
}
for (int k = 0; k < top; k ++)
arc[path[k]]. flow -= minflow, arc[path[k]^1]. flow += minflow;
maxflow += minflow;
top = mink;
i = arc[path[top]]. u;
}
for (j = cur[i]; j != -1; cur[i] = j = arc[j].next){
int v = arc[j]. v;
if (arc[j].flow && dep[v] == dep[i] + 1)
break;
}
if (j != -1){
path[top ++] = j;
i = arc[j]. v;
}
else{
if (top == 0)   break;
dep[i] = -1;
i = arc[path[-- top]]. u;
}
}
}
return maxflow;
}
};
Dinic  dinic;
int mark[MAXV];
bool if_ mark[MAXV];
struct path{
int u, v;
}p[MAXE];
bool vis[MAXV];
int st[MAXV];   // St set
void dfs(int u){
vis[u] = 1;
st[u] = 1;
for (int i = dinic.head[u]; i != -1; i = dinic.arc[i].next){
if (dinic.arc[i].flow <= 0) continue;
int v = dinic. arc[i]. v;
if (!vis[v]){
dfs(v);
}
}
return ;
}
int main(){
int t;
scanf("%d", &t);
while(t --){
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i ++){
scanf("%d %d", &p[i].u, &p[i].v);
}
int k;
mem(mark, 0);
mem(if_mark, false);
scanf("%d", &k);
int maxn = 0;
for (int i = 0; i < k; i ++){
int u;
scanf("%d", &u);
scanf("%d", &mark[u]);
maxn = max(maxn, mark[u]);
if_ mark[u] = true;
}
int oi = ceil(log(maxn)/log(2));
for (int k = 0; k < oi; k ++){
dinic. init(n+2);
for (int i = 1; i <= n; i ++){
if (!if_mark[i])
)