id build() {?
??? //③将所有的与之相连的边极角排序。?
??? for (int i = 1; i <= n; i++) {?
??????? sort(vertex[i].begin(), vertex[i].end());?
??????? int ms = vertex[i].size();?
??? //④遍历每条入边。将其后继设为与之顺时针相邻的出边。也就是在G’中连一条从这个入边的点到其后继的有向边。?
??????? for (int j = 0; j < ms - 1; j++)?
??????????? nxt[vertex[i][j].in] = vertex[i][j + 1].out;?
??????? nxt[vertex[i][ms - 1].in] = vertex[i][0].out;?
??? }?
??? int ms = m << 1 | 1;?
??? memset(belong, -1, sizeof(belong));?
??? cnt = 0;?
??? //⑤在G'中就是一些不相交的有向环。每个有向环就对应一个区域。找出了所有的区域，我们要的那张图就简单了。?
??? for (int i = 0; i <= ms; i++)?
??????? if (belong[i] == -1 && ++cnt > 0)?
??????????? find(i, i);?
??? //构不成平面的边,会形成一个特殊的区域，相当于进去死胡同再出来。但是答案不会受到影响，所以直接忽略。?
}?
double work() {?
??? int a, b;?
??? sp.init();?
??? //⑥根据对偶图构图，求得s-t之间最短路即是对应的最小割?
??? for (int i = 0; i < m; i++) {?
??????? a = belong[i << 1];?
??????? b = belong[i << 1 | 1];?
??????? sp.add(a, b, cap[i]);?
??????? sp.add(b, a, cap[i]);?
??? }?
??? a = belong[m << 1];?
??? b = belong[m << 1 | 1];?
??? return sp.solve(a, b);?
}?
int main() {?
??? int cas;?
??? scanf("%d", &cas);?
??? while (cas--) {?
??????? init();?
??????? build();?
??????? printf("%.0f\n", work());?
??? }?
??? return 0;?
}?
?
|