【題意】給出一個無向圖，每個點有一個標號mark[i]，不同點可能有相同的標號。對于一條邊(u, v)，它的權值定義為mark[u] xor mark[v]。現在一些點的標號已定，請決定剩下點的標號，使得總的邊權和最小。（0 < N <= 500, 0 <= M <= 3000, 0 <=?mark[i] <= 2^31-1） 胡伯濤神牛《最小割模型在信息學競賽中的應用》中的例題。非常好的一道題！非常推薦！ 【思路】 我們把問題數學化就是： ?Minimum ?sigma(w_e) = sigma_{(u, v)∈E?}( mark(u) xor mark(v) ) 對于異或問題，我們發現這樣的二進制按位運算各個二進制位之間是互不影響的，所以我們可以一位一位的做這類題。 那么我們的式子又可以進一步轉化為： Minimum ?sigma_{(u, v)∈E}?{ sigma_i=0~oo(2^i)?? sigma(mark(u, i) xor mark(v, i))?} 這樣我們就把mark的限制加強了：只可能是0或1。即這些點將分成兩類。 再觀察我們發現，xor運算，只有當u、v不同時結果才為1，即這樣的有效邊的兩端點一定屬于不同點集。這像什么？不就是割邊嘛！~而題目正好又是要求最小，這樣問題便轉化為最小割了~ ? ?（要注意培養這種問題轉化和模型發現的能力！） 那么具體的最小割網絡G_N模型：建一個源點，向每一個標號為1的點連一條oo流量的邊（后面解釋為什么源點連標號1的點）；建一個匯點，向每一個標號為0的點連一條oo流量的邊；原圖中的邊容量設為1加入到G_N中。求出來的最小割便是該二進制位下的標號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; }

轉載于:https://www.cnblogs.com/AbandonZHANG/p/4114268.html

總結

以上是生活随笔為你收集整理的SPOJ-OPTM Optimal Marks ★★(按位建图 最小割)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。