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;

queueque;
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