hdu 3435 A new Graph Game(最小费用最大流)

题意： 一个无向图（or 有向图）， 每一个点都必须属于一个圈， 并且只能属于一个圈， 求满足要求的最小费用。

比如：

1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
there are two cycles, (1->2->3->1) and (6->5->4->6) whose length is 20 + 22 = 42

像这样构成圈并且每个点只能属于一个圈的题， 可以转化成2 分图， 每个点只能属于一个圈， 那么出度和入度必定为1 ， 那么把一个点拆开i, i`， i控制入读， i` 控制出度， 流量只能为1 。 那么对于原来图中有的边 可以 i - > j`, j - > i`;连起来构图， 然后建立超级远点s，超级汇点t，s - > i ， i` - > t ; 然后求最小费用流。。这样就保证了每个点只能属于一个圈， 因为入读 == 出度 == 1 ；这类也问题可以 做为判断性问题出。

关键是拆点建图，把每个顶点拆成i和i+n。附加一个源点S和汇点T。

S与1~n建边，容量为1，花费为0；

n+1~n*2与T建边，容量为1，花费为0。

若ab右边，a与b+n建边，容量为1，花费为c,b与a+n建边，容量为1，花费为c。

求最小费用流。

最后判断时，因为每个点都存在某个双连通分量中，那么每个点（1~n）的总流量为0。若某个点的总流量不为0，输出NO。

否则，输出最小费用流。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define inf 0x3f3f3f3f const int maxn = 55555; using namespace std; queue
      
       que; struct node { int u,v,f,c,next; }edge[maxn]; int head[maxn]; bool vis[maxn]; int dis[maxn]; int pre[maxn]; int n,m,s,t,cnt; void add(int u,int v,int f,int c) { edge[cnt] = (struct node){u,v,f,c,head[u]}; head[u] = cnt++; edge[cnt] = (struct node){v,u,0,-c,head[v]}; head[v] = cnt++; } bool spfa() { int j; while(!que.empty()) que.pop(); memset(vis,false,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); memset(pre,-1,sizeof(pre)); vis[s]=true; dis[s]=0; que.push(s); while(!que.empty()) { int u=que.front(); que.pop(); vis[u]=false; for(j=head[u]; j!=-1; j=edge[j].next) { int v=edge[j].v; if(edge[j].f&&dis[u]+edge[j].c