UVA1349
题意: 给定一些有向带权边, 求出把这些边构造成一个个环, 总权值最小
解法:
对于带权的二分图的匹配问题可以用通过 KM 算法求解.
要求最大权匹配就是初始化 g[i][j] 为 0, 直接跑就可以;
要求最小权匹配就是初始化 g[i][j] 为 - INF, 加边的时候边权为负, 最后输出答案的相反数.
因为要求每个点恰好属于一个圈, 意味着每个点都有一个唯一的后继. 反过来, 只要每个点都有唯一的后继, 每个点一定属于某个圈.
唯一的是我们想到了二分图的概念, 我们对于每个点, 建立由 u 到 v 的二分图, 之后问题就转换成了二分图上的最小权完美匹配问题
- #include<bits/stdc++.h>
- #define REP(i, a, b) for(int i = (a); i <(b); i++)
- #define MEM(a,x) memset(a,x,sizeof(a))
- #define INF 0x3f3f3f3f
- #define MAXN 100+10
- using namespace std;
- struct KM {
- int n;
- int g[MAXN][MAXN];
- int Lx[MAXN], Ly[MAXN];
- int slack[MAXN];// 记录距 X 匹配到 Y 点还需要多少权值
- int match[MAXN];// 记录每个 X 点匹配到的 Y 集中的点
- bool S[MAXN], T[MAXN];
- void init(int n) {
- this->n = n;
- for (int i = 0; i <n; i++)
- for (int j = 0; j < n; j++)
- g[i][j] = -INF;
- // 注意这里如果是求最大权值匹配和就赋值为 0
- // 最小权值匹配和就是 - INF
- }
- void add_Edge(int u, int v, int val) {
- g[u][v] = max(g[u][v], val);
- }
- bool dfs(int i) {
- S[i] = true;
- for (int j = 0; j < n; j++) {
- if (T[j]) continue;
- int tmp = Lx[i] + Ly[j] - g[i][j];
- if (!tmp) {
- T[j] = true;
- if (match[j] == -1 || dfs(match[j])) {
- match[j] = i;
- return true;
- }
- }
- else slack[j] = min(slack[j], tmp);
- }
- return false;
- }
- void update() {
- int a = INF;
- for (int i = 0; i < n; i++)
- if (!T[i]) a = min(a, slack[i]);
- for (int i = 0; i < n; i++) {
- if (S[i]) Lx[i] -= a;
- if (T[i]) Ly[i] += a;
- }
- }
- void km() {
- for (int i = 0; i < n; i++) {
- match[i] = -1;
- Lx[i] = -INF; Ly[i] = 0;
- for (int j = 0; j < n; j++)
- Lx[i] = max(Lx[i], g[i][j]);
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) slack[j] = INF;
- while (1) {
- for (int j = 0; j < n; j++) S[j] = T[j] = false;
- if (dfs(i)) break;
- else update();
- }
- }
- }
- }Men;
- int main() {
- int n;
- while (scanf("%d", &n) == 1 && n) {
- Men.init(n);
- REP(u, 0, n) {
- int v;
- while (scanf("%d", &v) && v) {
- int w; scanf("%d", &w);
- v--;
- Men.add_Edge(u, v, -w);
- }
- }
- Men.km();
- int ans = 0, flag = 1;
- REP(i, 0, n) {
- if (Men.g[Men.match[i]][i] == -INF) {
- // 有未匹配到, 就是不成功, 因为题目要求的是完美匹配
- flag = 0;
- break;
- }
- ans += Men.g[Men.match[i]][i];// 累加权值
- }
- if (!flag) printf("N\n");
- else printf("%d\n", -ans);// 最后是输出的是负数
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2751697.html