UVa 1349

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4095

题意：

给n个点（n≤99）的有向带权图，找若干个有向圈，使得每个点恰好属于一个圈。
要求权和尽量小。注意即使(u,v)和(v,u)都存在，它们的权值也不一定相同。

分析：

每个点恰好属于一个有向圈，意味着每个点都有一个唯一的后继。
反过来，只要每个点都有唯一的后继，每个点一定恰好属于一个圈。
把每个点i拆成Xi和Yi，原图中的有向边u->v对应二分图中的边Xu->Yv，
则题目转化为了这个二分图上的最小权完美匹配问题。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <vector>
 5 using namespace std;
 6 
 7 /// 结点下标从0开始，注意maxn
 8 struct MCMF {
 9     static const int maxn = 99 * 2 + 5;
10     static const int INF = 0x3f3f3f3f;
11     struct Edge {
12         int from, to, cap, flow, cost;
13     };
14 
15     int n, m;
16     vector<Edge> edges;
17     vector<int> G[maxn];
18     int inq[maxn]; // 是否在队列中
19     int d[maxn]; // Bellman-Ford
20     int p[maxn]; // 上一条弧
21     int a[maxn]; // 可改进量
22 
23     void init(int n) {
24         this->n = n;
25         for(int i = 0; i < n; i++) G[i].clear();
26         edges.clear();
27     }
28     void AddEdge(int from, int to, int cap, int cost) {
29         edges.push_back((Edge){from, to, cap, 0, cost});
30         edges.push_back((Edge){to, from, 0, 0, -cost});
31         m = edges.size();
32         G[from].push_back(m-2);
33         G[to].push_back(m-1);
34     }
35     bool BellmanFord(int s, int t, int& flow, int& cost) {
36         for(int i = 0; i < n; i++) d[i] = INF;
37         memset(inq, 0, sizeof(inq));
38         d[s] = 0;  inq[s] = 1;  p[s] = 0;  a[s] = INF;
39         queue<int> Q;
40         Q.push(s);
41         while(!Q.empty()) {
42             int u = Q.front();  Q.pop();
43             inq[u] = 0;
44             for(int i = 0; i < G[u].size(); i++) {
45                 Edge& e = edges[G[u][i]];
46                 if(e.cap > e.flow && d[e.to] > d[u] + e.cost) {
47                     d[e.to] = d[u] + e.cost;
48                     p[e.to] = G[u][i];
49                     a[e.to] = min(a[u], e.cap - e.flow);
50                     if(!inq[e.to]) {
51                         Q.push(e.to);
52                         inq[e.to] = 1;
53                     }
54                 }
55             }
56         }
57         if(d[t] == INF) return false;
58         //if(flow + a[t] > flow_limit) a[t] = flow_limit - flow;
59         flow += a[t];
60         cost += d[t] * a[t];
61         for(int u = t; u != s; u = edges[p[u]].from) {
62             edges[p[u]].flow += a[t];
63             edges[p[u]^1].flow -= a[t];
64         }
65         return true;
66     }
67     // 需要保证初始网络中没有负权圈
68     pair<int,int> MincostMaxflow(int s, int t) {
69         int flow = 0, cost = 0;
70         while(BellmanFord(s, t, flow, cost));
71         //while(flow < flow_limit && BellmanFord(s, t, flow_limit, flow, cost));
72         return make_pair(flow, cost);
73     }
74 } mm;
75 
76 int main() {
77     int n;
78     while(scanf("%d", &n) && n) {
79         mm.init(n*2+2);
80         int start = 0, finish = n*2+1;
81         for(int j, d, i = 1; i <= n; i++) {
82             mm.AddEdge(start, i, 1, 0);
83             mm.AddEdge(i+n, finish, 1, 0);
84             while(true) {
85                 scanf("%d", &j);
86                 if(j == 0) break;
87                 scanf("%d", &d);
88                 mm.AddEdge(i, j+n, 1, d);
89             }
90         }
91         pair<int,int> p = mm.MincostMaxflow(start, finish);
92         if(p.first < n) printf("N
");
93         else printf("%d
", p.second);
94     }
95     return 0;
96 }