题目大意

　　有一张$n$个结点，$m$条混合边的图（$1 \leq n \leq 200$，$1 \leq m \leq 1000$），求这张图是否存在欧拉回路。

题解

　　因为有混合边，所以我们要先给无向边随机定向，然后再调整方向。

　　随机定向之后，我们就得到一张有向图。

　　我们记录每个结点的入度$ind[i]$和出度$outd[i]$，根据欧拉路的性质可以得到，当$ind[i] + outd[i]$为奇数时，一定不存在欧拉路。

　　对于建边过程，因为原有的有向边不能变向，所以我们可以忽略，只需要将读入的无向边随机定向成有向边即，设容量为$1$即可（每条边只能走一次）。

　　对于每一个$ind[i] \leq outd[i]$的结点$i$，我们都从源点$s$向$i$连一条有向边，容量为$\frac{outd[i] - ind[i]}{2}$；对于$ind[i] > outd[i]$的结点$i$，从$i$向$t$连一条有向边，容量为$\frac{ind[i] - outd[i]}{2}$。这两种边的含义是连接结点$i$的边中，需要变向的边数。

　　显然，我们从$s$开始跑一次最大流，最后判断与$s$或$t$相连的边是否满流即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#define MAX_N (200 + 5)

#define MAX_M (1000 + 5)

using namespace std;

struct Edge

{

    int to;

    int weight;

    int next;

};

int T;

int n, m;

int s, t;

int h[MAX_N], tot = ;

Edge e[MAX_N + MAX_M << ];

int ind[MAX_N], outd[MAX_N];

int dep[MAX_N];

int cur[MAX_N];

queue <int> q;

int maxflow;

inline void AddEdge(int u, int v, int w)

{

    e[++tot].to = v;

    e[tot].weight = w;

    e[tot].next = h[u];

    h[u] = tot;

    return;

};

bool BFS()

{

    memset(dep, 0x7f, sizeof dep);

    memcpy(cur, h, sizeof cur);

    q.push(s);

    dep[s] = ;

    int u, v, w;

    while(!q.empty())

    {

        u = q.front();

        q.pop();

        for(int i = h[u]; i; i = e[i].next)

        {

            v = e[i].to;

            w = e[i].weight;

            if(dep[v] > dep[u] +  && w)

            {

                dep[v] = dep[u] + ;

                q.push(v);

            }

        }

    }

    return dep[t] != 0x7f7f7f7f;

}

int DFS(int u, int flow)

{

    if(u == t)

    {

        maxflow += flow;

        return flow;

    }

    int v, w;

    int tmp, sum = ;

    for(int i = cur[u]; i && flow; i = e[i].next)

    {

        cur[u] = i;

        v = e[i].to;

        w = e[i].weight;

        if(dep[v] == dep[u] +  && w && (tmp = DFS(v, min(flow, w))))

        {

            e[i].weight -= tmp;

            e[i ^ ].weight += tmp;

            sum += tmp;

            flow -= tmp;

        }

    }

    return sum;

}

void Dinic()

{

    while(BFS()) DFS(s, 0x7f7f7f7f);

    return;

}

int main()

{

    scanf("%d", &T);

    while(T--)

    {

        memset(h, , sizeof h);

        memset(ind, , sizeof ind);

        memset(outd, , sizeof outd);

        tot = ;

        maxflow = ;

        scanf("%d%d", &n, &m);

        s = ;

        t = n + ;

        int u, v, d;

        for(int i = ; i <= m; ++i)

        {

            scanf("%d%d%d", &u, &v, &d);

            ++outd[u];

            ++ind[v];

            if(!d)

            {

                AddEdge(u, v, );

                AddEdge(v, u, );

            }

        }

        bool isEuler = true;

        for(int i = ; i <= n; ++i)

        {

            if(ind[i] + outd[i] & )

            {

                isEuler = false;

                break;

            }

        }

        if(!isEuler)

        {

            printf("impossible\n");

            continue;

        }

        int tmp = tot;

        for(int i = ; i <= n; ++i)

        {

            if(ind[i] <= outd[i])

            {

                AddEdge(s, i, outd[i] - ind[i] >> );

                AddEdge(i, s, );

            }

            else

            {

                AddEdge(i, t, ind[i] - outd[i] >> );

                AddEdge(t, i, );

            }

        }

        Dinic();

        for(int i = tmp + ; i <= tot; i += )

        {

            if(e[i].weight)

            {

                isEuler = false;

                break;

            }

        }

        if(!isEuler) printf("impossible\n");

        else printf("possible\n");

    }

    return ;

}

参考程序

巴特西

【题解】Sigitseeing Tour

题目大意

题解

最新文章

热门文章