题意：有若干城市组成一张有向图权值是花费，要你设计一个公交线路图是每个城市都经过一遍，然后要求总的花费最少。线路数量不限制只要覆盖到所有城市有且仅有一次就可以，输出最小费用。
思路：liurujia分在二分图里面的题目，第一眼看上去就像是费用流的题，想了一个多小时二分图做法没成功，还是用费用流a了。仔细观察我们可以发现设计出来的线路图必满足最大匹配数等于城市数（二分图两边都为城市）然后在这基础上费用最小。接下来就是建图套模版了。
补充：其实直接KM就能解决此题。。果断对算法理解还不到位。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-26 00:33 5 * Filename : uva_1349.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int MAXN = 10000; 34 const int MAXM = 100000; 35 struct Edge{int to,next,cap,flow,cost;}edge[MAXM]; 36 int head[MAXN],tol; 37 int pre[MAXN],dis[MAXN]; 38 bool vis[MAXN]; 39 int N;//节点总个数，节点编号从0~N-1 40 41 void init(int n) 42 { 43 N = n; 44 tol = 0; 45 memset(head,-1,sizeof(head)); 46 } 47 48 void addedge(int u,int v,int cap,int cost) 49 { 50 edge[tol].to = v; 51 edge[tol].cap = cap; 52 edge[tol].cost = cost; 53 edge[tol].flow = 0; 54 edge[tol].next = head[u]; 55 head[u] = tol++; 56 edge[tol].to = u; 57 edge[tol].cap = 0; 58 edge[tol].cost = -cost; 59 edge[tol].flow = 0; 60 edge[tol].next = head[v]; 61 head[v] = tol++; 62 } 63 bool spfa(int s,int t) 64 { 65 queue<int>q; 66 for(int i = 0; i < N; i++) 67 { 68 dis[i] = INF; 69 vis[i] = false; 70 pre[i] = -1; 71 } 72 dis[s] = 0; 73 vis[s] = true; 74 q.push(s); 75 while(!q.empty()) 76 { 77 int u = q.front(); 78 q.pop(); 79 vis[u] = false; 80 for(int i = head[u]; i != -1; i = edge[i].next) 81 { 82 int v = edge[i].to; 83 if(edge[i].cap > edge[i].flow && 84 dis[v] > dis[u] + edge[i].cost ) 85 { 86 dis[v] = dis[u] + edge[i].cost; 87 pre[v] = i; 88 if(!vis[v]) 89 { 90 vis[v] = true; 91 q.push(v); 92 } 93 } 94 } 95 } 96 if(pre[t] == -1)return false; 97 else return true; 98 } 99 //返回的是最大流，cost存的是最小费用 100 int minCostMaxflow(int s,int t,int &cost) 101 { 102 int flow = 0; 103 cost = 0; 104 while(spfa(s,t)) 105 { 106 int Min = INF; 107 for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) 108 { 109 if(Min > edge[i].cap - edge[i].flow) 110 Min = edge[i].cap - edge[i].flow; 111 } 112 for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) 113 { 114 edge[i].flow += Min; 115 edge[i^1].flow -= Min; 116 cost += edge[i].cost * Min; 117 } 118 flow += Min; 119 } 120 return flow; 121 } 122 123 int main() 124 { 125 // freopen("in.txt", "r", stdin); 126 127 int n, a, b; 128 while(scanf("%d", &n)!=EOF && n){ 129 init(2*n+2); 130 for(int i=0; i<n; i++){ 131 while(scanf("%d", &a)!=EOF && a){ 132 scanf("%d", &b); 133 addedge(i, a-1+n, 1, b); 134 } 135 } 136 for(int i=0; i<n; i++){ 137 addedge(2*n, i, 1, 0); 138 addedge(n+i, 2*n+1, 1, 0); 139 } 140 int cost, ans = minCostMaxflow(N-2, N-1, cost); 141 if(ans == n) printf("%d ", cost); 142 else printf("N "); 143 } 144 return 0; 145 }