给出一个 n 个点的有向图，找若干个圈，是的每个结点恰好属于一个圈。要求总长度尽量小。
三倍经验题 Uva 12264，HDU 1853
这题有两种解法，一是匹配：
每个点只在一个圈中，则他有唯一的前驱和后继，也就是入度为1，出度为1，拆成 入度点和出度点，跑最小全匹配，因为是匹配，这样就保证了他在唯一的一个圈中，但是刘汝佳的板子有个问题，就是他会产生被迫的匹配，瞎起的名字，注意有这样的原本不存在的边，就说明无解。再次熟悉一下顶标。太久没写了~~~~
而是费用流：MCMF
就是中间cap = c，有无解就是看流量是否为 n ，是的，就是最小费用。
#includeusing namespace std;const int maxn = 100;const int inf = 1<<30;int W[maxn][maxn],n;int Lx[maxn],Ly[maxn]; ///顶标int lefts[maxn]; ///left[i] 为右边第 i 个点的标号bool S[maxn],T[maxn]; ///S,T左右第 i 个点是否标记bool match(int i) { S[i] = true; for(int j = 1; j <= n; j++) if(Lx[i]+Ly[j]==W[i][j]&&!T[j]) { T[j] = true; if(!lefts[j]||match(lefts[j])) { lefts[j] = i; return true; } } return false;}void update() { int a = 1<<30; for(int i = 1; i <= n; i++) if(S[i]) for(int j = 1; j <= n; j++) if(!T[j]) a = min(a,Lx[i]+Ly[j]-W[i][j]); for(int i = 1; i <= n; i++) { if(S[i]) Lx[i]-=a; if(T[i]) Ly[i]+=a; }}void KM() { for(int i = 1; i <= n; i++) { lefts[i] = Lx[i] = Ly[i] = 0; for(int j = 1; j <= n; j++) Lx[i] = max(Lx[i],W[i][j]); } for(int i=1;i<=n;i++) { for(;;) { for(int j=1;j<=n;j++) S[j] = T[j] = 0; if(match(i)) break; else update(); } }}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d",&n),n) { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) W[i][j] = -inf; memchr(W,-inf,sizeof(W)); for(int u = 1; u <= n ; u++) { int v,c; while(scanf("%d",&v),v) { scanf("%d",&c); W[u][v] = max(W[u][v],-c); } } KM(); bool flag = true; int ans = 0; for(int j = 1; j <= n; j++) { int i = lefts[j]; if(W[i][j]==-inf) { flag = false; break; } ans+= -W[i][j]; } if(flag==false) puts("N"); else printf("%d\n",ans); } return 0;}