题意：给定一个有向带权图，使得每一个点都在一个环上，而且权之和最小。

分析：每个点在一个环上，入度 = 出度 = 1，拆点入点，出点，s到所有入点全部满载的最小费用MCMF;

#include 
     
      using namespace std;const int maxn = 105*2;const int INF = 0x3f3f3f3f;typedef pair
      
        pii;struct Edge{    int from, to, cap, flow, cost;};struct MCMF{    int n, m;    vector
       
         edges;    vector
        
          G[maxn];    bool inq[maxn];         // 是否在队列中    int d[maxn];           // Bellman-Ford    int p[maxn];           // 上一条弧    int a[maxn];           // 可改进量    void init(int n)    {        this->n = n;        for(int i = 0; i < n; i++) G[i].clear();        edges.clear();    }    void AddEdge(int from, int to, int cap, int cost)    {        edges.push_back((Edge)        {            from, to, cap, 0, cost        });        edges.push_back((Edge)        {            to, from, 0, 0, -cost        });        m = edges.size();        G[from].push_back(m-2);        G[to].push_back(m-1);    }    bool BellmanFord(int s, int t, int &flow, long long& cost)    {        memset(inq,0,sizeof(inq));        for(int i=0;i
         

Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(e.cap > e.flow && d[e.to] > d[u] + e.cost) { d[e.to] = d[u] + e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; } } } } if(d[t] == INF) return false; //s-t 不连通，失败退出 flow += a[t]; cost += (long long)d[t] * (long long)a[t]; int u = t; while(u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return true; } pair

Mincost(int s, int t) { long long cost = 0; int flow = 0; while(BellmanFord(s, t, flow, cost)); return pair

{flow,cost}; }}sol;int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int s = 0,t=2*n+1; sol.init(2*n+2); for(int i=1;i<=n;i++) sol.AddEdge(s,i,1,0); for(int i=n+1;i<=2*n;i++) sol.AddEdge(i,t,1,0); for(int i=0;i