题解：城市观光巴士路线规划（欧拉回路问题）

这段代码解决的是一个关于判断图中是否存在欧拉回路的问题。具体来说，题目要求判断是否能规划一条巴士路线，使得每条街道恰好被访问一次，并且巴士回到起点。这是一个经典的图论问题，涉及到欧拉回路的存在性判断。

问题分析

题目给定一个城市的街道网络，其中一些街道是单向的，另一些是双向的。需要判断是否存在一条回路，使得：

1. 每条街道恰好被访问一次
2. 巴士回到起点

欧拉回路存在的条件

对于一个混合图（包含单向边和双向边），存在欧拉回路的条件是：

1. 所有顶点的度数（入度+出度）必须是偶数
2. 对于双向边，可以通过适当定向，使得每个顶点的入度等于出度

代码思路

1. 预处理：检查所有顶点的度数是否为偶数。如果存在奇度顶点，直接判定为不可能。
2. 网络流建模：对于双向边，构建一个网络流模型，通过最大流来判断是否可以合理定向这些边，使得所有顶点的入度等于出度。
3. 最大流计算：使用Dinic算法计算最大流，判断是否存在可行解。

代码详细解释

#include<cstdio>
#include<cstring>
#include<math.h>
#include<queue>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int N=2*1e2+10;
const int M=2*1e5+10;
const int INF=0x3f3f3f3f;
int m,s;
struct node
{
    int nex;
    int to,w;
} side[M];
int fir[N],tot;///邻接表建图
int ind[N];///记录入度，出度
int level[N];///记录每一个点的层次
int cut[M];

// 添加边（正向边和反向边）
void Inx(int x,int y,int z)
{
    side[++tot].to=y,side[tot].w=z;
    side[tot].nex=fir[x];
    fir[x]=tot;
}

// BFS构建层次网络
int bfs()
{
    memset(level,-1,sizeof(level));
    queue<int>Q;
    level[0]=1;
    Q.push(0);
    while(!Q.empty())
    {
        int u=Q.front();
        if(u==m+1)
            break;
        Q.pop();
        for(int i=fir[u]; ~i; i=side[i].nex)
        {
            if(side[i].w&&level[side[i].to]<0)
            {
                level[side[i].to]=level[u]+1;///构建层次网络
                Q.push(side[i].to);
            }
        }
    }
    return level[m+1]!=-1;
}

// DFS寻找增广路径
int dfs(int u,int low)
{
    if(u==m+1)
        return low;
    int temp=0,a;
    for(int &i=cut[u]; ~i; i=side[i].nex)///i的改变带着fir[u]的改变，提高效率
    {
        if(side[i].w&&level[side[i].to]==level[u]+1&&(a=dfs(side[i].to,min(low,side[i].w))))
        {
            temp+=a;
            side[i].w-=a;
            side[i^1].w+=a;
            low-=a;
            if(!low)
                break;
        }
    }
    if(temp==0)
        level[u]=-1;///走到u不能走
    return temp;
}

// Dinic算法计算最大流
int dinic()
{
    int ans=0;
    while(bfs())///找到一条增广路
    {
        for(int i=0; i<=m+1; i++)
            cut[i]=fir[i];
        ans+=dfs(0,INF);
    }
    return ans;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        tot=-1;
        memset(ind,0,sizeof(ind));
        memset(fir,-1,sizeof(fir));
        scanf("%d%d",&m,&s);
        
        // 读入街道信息，处理入度和出度
        while(s--)
        {
            int x,y,d;
            scanf("%d%d%d",&x,&y,&d);
            if(x==y)
                continue;
            ind[x]--,ind[y]++;///出度--，入度++
            if(!d)///无向边
            {
                Inx(x,y,1);///把无向边随便规定一个方向
                Inx(y,x,0);
            }
        }
        
        // 检查所有顶点的度数是否为偶数
        bool bo=true;
        for(int i=1; i<=m; i++)
        {
            if(ind[i]&1)///欧拉图
            {
                bo=false;
                break;
            }
        }
        
        if(!bo)
            printf("impossible\n");
        else
        {
            int sum=0;
            // 构建网络流模型
            for(int i=1; i<=m; i++)
            {
                if(ind[i]<0)///出>入
                {
                    Inx(0,i,(-ind[i])>>1);
                    Inx(i,0,0);
                }
                if(ind[i]>0)//入>出
                {
                    Inx(i,m+1,ind[i]>>1);
                    Inx(m+1,i,0);
                    sum+=(ind[i]>>1);
                }
            }
            
            // 计算最大流
            int mxx_flow=dinic();
            
            // 判断是否存在欧拉回路
            if(mxx_flow==sum)
                printf("possible\n");
            else
                printf("impossible\n");
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(T \times m^2 \times s)$，其中$T$是测试用例数量，$m$是顶点数，$s$是边数。每次测试用例需要构建网络并计算最大流。
• 空间复杂度：$O(m + s)$，主要用于存储邻接表和网络流模型。