传送门
题意：判断混合图是否存在欧拉回路。
真是一道好题。 把该图的无向边随便定向， 计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度= 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以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 连接的点，自然早在开始就已经满足入=出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
由于这道题只判断是否存在，只需判断满流即可。
Code #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int Maxn=2e2+50; const int Maxm=5e3+50; const int INF=0x3f3f3f3f; inline int read() { char ch=getchar();int i=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();} return i*f; } int n,m,des,cur[Maxn],lev[Maxn],last[Maxn],in[Maxn],out[Maxn],to[Maxm],before[Maxm],cap[Maxm],ecnt=1; inline void add(int x,int y,int c) { before[++ecnt]=last[x];last[x]=ecnt;to[ecnt]=y;cap[ecnt]=c; before[++ecnt]=last[y];last[y]=ecnt;to[ecnt]=x;cap[ecnt]=0; } inline bool bfs() { static int que[Maxn],head,tail; for(int i=0;i<=des;i++)lev[i]=-1,cur[i]=last[i]; que[head=tail=1]=0;lev[0]=0; while(head<=tail) { int now=que[head++]; for(int e=last[now];e;e=before[e]) { int v=to[e]; if(lev[v]!=-1||cap[e]==0)continue; lev[v]=lev[now]+1;que[++tail]=v; if(v==des)return true; } } return false; } inline int dinic(const int &now,const int &flow) { if(now==des)return flow; int res=0; for(int &e=cur[now];e;e=before[e]) { int v=to[e]; if(cap[e]==0||lev[v]<=lev[now])continue; int o=dinic(v,min(flow-res,cap[e])); if(o) { cap[e]-=o;cap[e^1]+=o;res+=o; if(res==flow)break; } } if(res!=flow)lev[now]=-1; return res; } int main() { int T=read(); while(T--) { memset(last,0,sizeof(last)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); ecnt=1; n=read(),m=read();des=n+1; for(int i=1;i<=m;i++) { int x=read(),y=read(),d=read(); in[y]++;out[x]++; if(!d)add(x,y,1); } int ans=0,bz=1,all=0; for(int i=1;i<=n&&bz;i++) { if(in[i]!=out[i]) { if(in[i]>out[i]) { int t=in[i]-out[i]; if(t&1)bz=0; else add(i,des,t/2),all+=t; } else { int t=out[i]-in[i]; if(t&1)bz=0; else add(0,i,t/2); } } } all/=2; if(!bz)puts("impossible"); else { while(bfs())ans+=dinic(0,INF); if(ans==all)puts("possible"); else puts("impossible"); } } }