UVA1349
题意：给定一些有向带权边，求出把这些边构造成一个个环，总权值最小
解法：
对于带权的二分图的匹配问题可以用通过KM算法求解。
要求最大权匹配就是初始化g[i][j]为0，直接跑就可以；
要求最小权匹配就是初始化g[i][j]为-INF，加边的时候边权为负，最后输出答案的相反数。
因为要求每个点恰好属于一个圈，意味着每个点都有一个唯一的后继。 反过来，只要每个点都有唯一的后继，每个点一定属于某个圈。
唯一的是我们想到了二分图的概念，我们对于每个点，建立由u到v的二分图， 之后问题就转换成了二分图上的最小权完美匹配问题
1 #include2 #define REP(i, a, b) for(int i = (a); i < (b); i++) 3 #define MEM(a,x) memset(a,x,sizeof(a)) 4 #define INF 0x3f3f3f3f 5 #define MAXN 100+10 6 using namespace std; 7 8 struct KM { 9 int n; 10 int g[MAXN][MAXN]; 11 int Lx[MAXN], Ly[MAXN]; 12 int slack[MAXN];//记录距X匹配到Y点还需要多少权值 13 int match[MAXN];//记录每个X点匹配到的Y集中的点 14 bool S[MAXN], T[MAXN]; 15 16 void init(int n) { 17 this->n = n; 18 for (int i = 0; i < n; i++) 19 for (int j = 0; j < n; j++) 20 g[i][j] = -INF; 21 //注意这里如果是求最大权值匹配和就赋值为0 22 //最小权值匹配和就是—INF 23 } 24 25 void add_Edge(int u, int v, int val) { 26 g[u][v] = max(g[u][v], val); 27 } 28 29 bool dfs(int i) { 30 S[i] = true; 31 for (int j = 0; j < n; j++) { 32 if (T[j]) continue; 33 int tmp = Lx[i] + Ly[j] - g[i][j]; 34 if (!tmp) { 35 T[j] = true; 36 if (match[j] == -1 || dfs(match[j])) { 37 match[j] = i; 38 return true; 39 } 40 } 41 else slack[j] = min(slack[j], tmp); 42 } 43 return false; 44 } 45 46 void update() { 47 int a = INF; 48 for (int i = 0; i < n; i++) 49 if (!T[i]) a = min(a, slack[i]); 50 for (int i = 0; i < n; i++) { 51 if (S[i]) Lx[i] -= a; 52 if (T[i]) Ly[i] += a; 53 } 54 } 55 56 void km() { 57 for (int i = 0; i < n; i++) { 58 match[i] = -1; 59 Lx[i] = -INF; Ly[i] = 0; 60 for (int j = 0; j < n; j++) 61 Lx[i] = max(Lx[i], g[i][j]); 62 } 63 for (int i = 0; i < n; i++) { 64 for (int j = 0; j < n; j++) slack[j] = INF; 65 while (1) { 66 for (int j = 0; j < n; j++) S[j] = T[j] = false; 67 if (dfs(i)) break; 68 else update(); 69 } 70 } 71 } 72 }Men; 73 74 int main() { 75 int n; 76 while (scanf("%d", &n) == 1 && n) { 77 Men.init(n); 78 REP(u, 0, n) { 79 int v; 80 while (scanf("%d", &v) && v) { 81 int w; scanf("%d", &w); 82 v--; 83 Men.add_Edge(u, v, -w); 84 } 85 } 86 87 Men.km(); 88 int ans = 0, flag = 1; 89 REP(i, 0, n) { 90 if (Men.g[Men.match[i]][i] == -INF) { 91 //有未匹配到，就是不成功，因为题目要求的是完美匹配 92 flag = 0; 93 break; 94 } 95 ans += Men.g[Men.match[i]][i];//累加权值 96 } 97 if (!flag) printf("N\n"); 98 else printf("%d\n", -ans);//最后是输出的是负数 99 }100 return 0;101 }