题干：
In Hanoi, there are N beauty-spots (2 <= N <= 200), connected by M one-way streets. The length of each street does not exceed 10000. You are the director of a travel agency, and you want to create some tours around the city which satisfy the following conditions:
Each of the N beauty-spots belongs to exactly one tour.Each tour is a cycle which consists of at least 2 places and visits each place once (except for the place we start from which is visited twice).The total length of all the streets we use is minimal.InputThe first line of input contains the number of testcases t (t <= 15). The first line of each testcase contains the numbers N, M. The next M lines contain three integers U V W which mean that there is one street from U to V of length W.
OutputFor each test case you shold output the minimal total length of all tours.
Example Input:26 91 2 52 3 53 1 103 4 124 1 84 6 115 4 75 6 96 5 45 81 2 42 1 71 3 103 2 103 4 104 5 105 3 105 4 3Output:4240Detailed explanation:Test 1:Tour #1: 1 - 2 - 3 - 1 --> Length = 20Tour #2: 6 - 5 - 4 - 6 --> Length = 22Test 2:Tour #1: 1 - 3 - 2 - 1 --> Length = 27Tour #2: 5 - 4 - 5 --> Length = 13题目大意：
把一张带权有向图划分成一个或多个环，使环的总权值最小。
解题报告：
类似于二分图的最小路径覆盖，拆点。把每个点 u 拆成两个点 u1 和 u2， 然后每条边 u->v 改写成 u1---v2，就得到了一个二分图最佳匹配的模型。 由于“把一张带权有向图划分成一个或多个环”其实 等价于“每一个点都保留一个入度和一个出度” ，而匹配模型正好能满足这一点。于是建图跑模板就可以了、、
AC代码：
#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<map>#include<vector>#include<set>#include<string>#include<cmath>#include<cstring>#define ll long longusing namespace std;const int MAXN = 70000;const int MAXM = 100005;const int INF = 0x3f3f3f3f;struct Edge {int to,next,cap,flow,cost;} edge[MAXM];int head[MAXN],tol;int pre[MAXN],dis[MAXN];bool vis[MAXN];int N;void init(int n) {N = n;tol = 0;memset(head, -1,sizeof(head));}void addedge(int u,int v,int cap,int cost) {edge[tol].to = v;edge[tol].cap = cap;edge[tol].cost = cost;edge[tol].flow = 0;edge[tol].next = head[u];head[u] = tol++;edge[tol].to = u;edge[tol].cap = 0;edge[tol].cost = -cost;edge[tol].flow = 0;edge[tol].next = head[v];head[v] = tol++;}bool spfa(int s,int t) {queue<int>q;for(int i = 0; i <= N; i++) {dis[i] = INF;vis[i] = false;pre[i] = -1;}dis[s] = 0;vis[s] = true;q.push(s);while(!q.empty()) {int u = q.front();q.pop();vis[u] = false;for(int i = head[u]; i !=-1; i = edge[i].next) {int v = edge[i].to;if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ) {dis[v] = dis[u] + edge[i].cost;pre[v] = i;if(!vis[v]) {vis[v] = true;q.push(v);}}}}if(pre[t] ==-1)return false;else return true;}int minCostMaxflow(int s,int t,int &cost) {int flow = 0;cost = 0;while(spfa(s,t)) {int Min = INF;for(int i = pre[t]; i !=-1; i = pre[edge[i^1].to]) {if(Min > edge[i].cap-edge[i].flow)Min = edge[i].cap-edge[i].flow;}for(int i = pre[t]; i !=-1; i = pre[edge[i^1].to]) {edge[i].flow += Min;edge[i^1].flow-= Min;cost += edge[i].cost * Min;}flow += Min;}return flow;}int main(){int n,m;int t;scanf("%d",&t);while(t--) {scanf("%d%d",&n,&m);init(2*n+1);int st=0,ed=2*n+1;for(int i = 1,a,b,w; i<=m; i++) {scanf("%d%d%d",&a,&b,&w);addedge(a,b+n,1,w);}for(int i = 1; i<=n; i++) addedge(st,i,1,0);for(int i = n+1; i<=2*n; i++) addedge(i,ed,1,0);int cost;int ans = minCostMaxflow(st,ed,cost);printf("%d\n",cost);}return 0 ;}
