poj1637 Sightseeing tour，混合圖的歐拉回路問題，最大流解

poj1637 Sightseeing tour，混合圖的歐拉回路問題，最大流解

混合圖的歐拉回路問題

題目地址

歐拉回路問題

1 定義

歐拉通路 (Euler tour)——通過圖中每條邊一次且僅一次，並且過每一頂點的通路。

歐拉回路 (Euler circuit)——通過圖中每條邊一次且僅一次，並且過每一頂點的回路。

歐拉圖——存在歐拉回路的圖。

2 無向圖是否具有歐拉通路或回路的判定

G有歐拉通路的充分必要條件為：G 連通，G中只有兩個奇度頂點(它們分別是歐拉通路的兩個端點)。

G有歐拉回路(G為歐拉圖)：G連通，G中均為偶度頂點。


3 有向圖是否具有歐拉通路或回路的判定

D有歐拉通路：D連通，除兩個頂點外，其余頂點的入度均等於出度，這兩個特殊的頂點中，一個頂點的入度比出度大1，另一個頂點的入度比出度小1。

D有歐拉回路(D為歐拉圖)：D連通，D中所有頂點的入度等於出度。

4 混合圖

混合圖也就是無向圖與有向圖的混合，即圖中的邊既有有向邊也有無向邊。


5 混合圖歐拉回路

混合圖歐拉回路用的是網絡流求解
把該圖的無向邊隨便定向，計算每個點的入度和出度。如果有某個點出入度之差為奇數，那麼肯定不存在歐拉回路。因為歐拉回路要求每點入度 = 出度，也就是總度數為偶數，存在奇數度點必不能有歐拉回路。 現在每個點入度和出度之差均為偶數。將這個偶數除以 2，得 x。即是說，對於每一個點，只要將 x 條邊反向（入>出就是變入，出>入就是變出），就能保證出 = 入。如果每個點都是出 = 入，那麼很明顯，該圖就存在歐拉回路。 現在的問題就變成了：該改變哪些邊，可以讓每個點出 = 入？

構造網絡流模型。有向邊不能改變方向，直接刪掉。開始已定向的無向邊，定的是什麼向，就把網絡構建成什麼樣，邊長容量上限 1。另新建 s 和 t。對於入 > 出的點 u，連接邊(u, t)、容量為 x，對於出 > 入的點 v，連接邊(s, v)，容量為 x（注意對不同的點x不同）。之後，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。查看流值分配，將所有流量非 0（上限是 1，流值不是 0 就是1）的邊反向，就能得到每點入度 = 出度的歐拉圖。 由於是滿流，所以每個入 > 出的點，都有 x 條邊進來，將這些進來的邊反向，OK，入 = 出了。對於出 > 入的點亦然。那麼，沒和 s、t 連接的點怎麼辦？和s 連接的條件是出 > 入，和 t 連接的條件是入 > 出，那麼這個既沒和 s 也沒和 t 連接的點，自然早在開始就已經滿足入 = 出了。那麼在網絡流過程中，這些點屬於“中間點”。我們知道中間點流量不允許有累積的，這樣，進去多少就出來多少，反向之後，自然仍保持平衡。
所以，就這樣，混合圖歐拉回路問題就解決了。

#include
#include
#include
#include
#include
#include

using namespace std;

const int maxn = 500 + 5;
const int INF = 100000000;
struct Edge{
    int from, to, cap, flow;
};

struct Dinic{
    int n, m, s, t;
    vector edges;
    vector G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[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)
    {
        edges.push_back((Edge){from, to, cap, 0});
        edges.push_back((Edge){to, from, 0, 0});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis, 0, sizeof vis );
        queue Q;
        Q.push(s);
        vis[s] = 1;
        d[s] = 0;
        while(!Q.empty())
        {
            int x = Q.front(); Q.pop();
            for(int i=0; i e.flow)
                {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x, int a)
    {
        if(x == t || a == 0) return a;
        int flow = 0, f;
        for(int& i = cur[x]; i0)
            {
                e.flow += f;
                edges[G[x][i]^1].flow -= f;
                flow += f;
                a -= f;
                if(a==0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s, int t)
    {
        this->s = s; this->t =t;
        int flow = 0;
        while(BFS()){
            memset(cur, 0, sizeof cur );
            flow += DFS(s, INF);
        }
        return flow;
    }
};

Dinic solver;

int in[maxn], out[maxn];


int main()
{
    int T, n, m, i, x, y, z;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        memset(in, 0, sizeof in );
        memset(out, 0, sizeof out );
        solver.init(n+1);
        for(i=0; iy
                solver.AddEdge(x, y, 1);
            }
        }
        bool ok = true;
        for(i=1; i<=n; ++i)
        if( abs(in[i]-out[i])&1)
        {
            ok = false;
            break;
        }

        if(ok){
            int s = 0, t = n+1;
            int Full_flow = 0;
            for(i=1; i<=n; ++i)
            {
                if(out[i]-in[i]>0)
                {
                    solver.AddEdge(s, i, (out[i]-in[i])/2);
                    Full_flow += (out[i]-in[i])/2;
                }else {
                    solver.AddEdge(i, t, (in[i] - out[i])/2);
                }
            }

            int Max_Flow = solver.Maxflow(s, t);
            if( Max_Flow != Full_flow)
                ok = false;
        }
        if(ok) puts("possible");
        else puts("impossible");
    }
    return 0;
}