[最小费用流]hdoj 1853：Cyclic Tour
大致题意：
? ? 给出一个有向图，每条路都有一个边长值。现在要在图中选出一些圈(回路)，使得 1，每个圈至少包含两个点。 2，每个节点只能属于其中一个圈。现在求这些圈的总长度最少是多少。
?
大致思路：
? ? 囧啊，此等水题居然想了半天没有想法，最后又钻到欧拉回路的死胡同里面去了。其实很简单，因为每个点都必须只属于一个圈，所以每个点的入读和出度肯定都是1。把每个点拆成两个点 i i'。从源点向每个点连一条边容量为1，费用为0，限制入度。从每个i'向汇点连边，容量为1，限制出度。如果原图中有一条边(u v)。则连接u->v'容量为1，费用为这条路的长度。最后对构出的图求出最小费用最大流就可以了。
? ??#include<cstdio>
#include<cstring>#include<iostream>using namespace std;const int inf=99999999;const int nMax=3000;const int mMax=200000;struct{ int u,v, cap, cost, next, re;}edge[mMax];int ans,maxf;int k,edgeHead[nMax];int que[nMax],pre[nMax],dis[nMax];bool vis[nMax],flag;int K;void addEdge(int u,int v,int ca,int co){////始点 终点 流量 花费 edge[k].v=v; edge[k].cap=ca; edge[k].cost=co; edge[k].next=edgeHead[u]; edge[k].re=k + 1; edgeHead[u]=k ++; edge[k].v=u; edge[k].cap=0; edge[k].cost=-co; edge[k].next=edgeHead[v]; edge[k].re=k - 1; edgeHead[v]=k ++;}bool spfa(int s,int t,int n){ //始点，终点，总点数 int i, head = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方 for(i = 0; i <= n; i ++){ dis[i] = inf;//////////// vis[i] = false; } dis[s] = 0; que[0] = s; vis[s] = true; while(head != tail){ int u = que[head]; for(i = edgeHead[u]; i != 0; i = edge[i].next){ int v = edge[i].v; if(edge[i].cap && dis[v] >dis[u] + edge[i].cost){//////// dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]){ vis[v] = true; que[tail ++] = v; if(tail == nMax) tail = 0; } } } vis[u] = false; head++; if(head ==nMax) head = 0; } if(dis[t] ==inf) return false;/////////// return true;}void end(int s,int t){ int u, p; for(u = t;u!=s;u=edge[edge[p].re].v){ p = pre[u]; edge[p].cap-=1; edge[edge[p].re].cap+=1; ans+=edge[p].cost; } maxf+=1; //总流量}int main(){ int n,m,i,s,t,a,b,c; while(scanf("%d%d",&n,&m)!=EOF){ k=1; s=0,t=2*n+1; memset(edgeHead,0,sizeof(edgeHead)); for(i=1;i<=n;i++){ addEdge(s,i,1,0); addEdge(i+n,t,1,0); } while(m--){ scanf("%d%d%d",&a,&b,&c); addEdge(a,b+n,1,c); } ans=0; maxf=0; while(spfa(s,t,2*n+2)){ end(s,t); } if(maxf!=n){ printf("-1\n"); } else{ printf("%d\n",ans); } } return 0;}?