混合图欧拉回路
首先先明确基本概念连通的无向图存在欧拉回路当且仅当不存在奇点连通的有向图当且仅当每个点入度=出度这道题我们显然应该当作连通的有向图来做这个问题的困难之处在于我不知道应该从无向边的什么方向来走那我们先假定一个走向,然后就变成了一个完全意义上的有向图,然后我们在进行调整假定完方向后,我们就算出每个点的入度出度,假如我们调整了了一条无向边的方向,那么对于一个端点入度会+1或-1,出度会-1或+1毫无疑问,假如一个点出度和入度和为奇数,那么我永远也无法调整得到这个点出度=入度 排除这个情况后,我们考虑将入度>出度的点和入度<出度的点化为两侧谈到调整,不难想到最大流的增广路调整,而这题正是用最大流做对于每条无向边(u,v),暂定方向为u-->v ,连边u-->v flow=1 (不用管原来的有向边)对于入度小于出度的点,从源点连一条到它的边,权值为(out-in)/2;出度小于入度的点,连一条它到汇点的权值为(in-out)/2 的边;然后我们跑最大流,每次对无向边的调整都对应从源点流1个流量向汇点最后我们只要判断源点到各个点是否满流即可,满流就是所有点出度都=入度当与源点相连的点(出度>入度的点)都满流后,与汇点相连的点(出度<入度)一定也满流因为不管怎么调整,图中总的入度肯定=总的出度1 type node=record 2 next,point,flow:longint; 3 end; 4 5 var edge:array[0..100010] of node; 6 d,cur,p,pre,numh,h,cd,rd:array[0..210] of longint; 7 len,s,t,x,y,z,i,k,n,m:longint; 8 f:boolean; 9 10 procedure add(x,y,z:longint); 11 begin 12 inc(len); 13 edge[len].point:=y; 14 edge[len].flow:=z; 15 edge[len].next:=p[x]; 16 p[x]:=len; 17 end; 18 19 function min(a,b:longint):longint; 20 begin 21 if a>b then exit(b) else exit(a); 22 end; 23 24 function sap:longint; 25 var u,i,j,neck,q,tmp:longint; 26 begin 27 u:=0; 28 sap:=0; 29 fillchar(numh,sizeof(numh),0); 30 fillchar(h,sizeof(h),0); 31 numh[0]:=t+1; 32 for i:=0 to t do 33 cur[i]:=p[i]; 34 neck:=10010; 35 while h[0]-1 do 40 begin 41 j:=edge[i].point; 42 if (edge[i].flow>0) and (h[u]=h[j]+1) then 43 begin 44 cur[u]:=i; 45 pre[j]:=u; 46 u:=j; 47 neck:=min(edge[i].flow,neck); 48 if u=t then 49 begin 50 sap:=sap+neck; 51 while u<>0 do 52 begin 53 u:=pre[u]; 54 j:=cur[u]; 55 dec(edge[j].flow,neck); 56 inc(edge[j xor 1].flow,neck); 57 end; 58 neck:=10010; 59 end; 60 break; 61 end; 62 i:=edge[i].next; 63 end; 64 if i=-1 then 65 begin 66 dec(numh[h[u]]); 67 if numh[h[u]]=0 then exit; 68 i:=p[u]; 69 q:=-1; 70 tmp:=t; 71 while i<>-1 do 72 begin 73 j:=edge[i].point; 74 if edge[i].flow>0 then 75 if h[j] 0 then 86 begin 87 u:=pre[u]; 88 neck:=d[u]; 89 end; 90 end; 91 end; 92 end; 93 94 begin 95 readln(k); 96 while k>0 do 97 begin 98 dec(k); 99 readln(n,m);100 fillchar(p,sizeof(p),255);101 fillchar(rd,sizeof(rd),0);102 fillchar(cd,sizeof(cd),0);103 len:=-1;104 for i:=1 to m do105 begin106 readln(x,y,z);107 if x=y then continue;108 inc(cd[x]);109 inc(rd[y]);110 if z=0 then111 begin112 add(x,y,1);113 add(y,x,0);114 end;115 end;116 t:=n+1;117 f:=false;118 s:=0;119 for i:=1 to n do120 begin121 if (cd[i]+rd[i]) mod 2=1 then122 begin123 f:=true;124 break;125 end;126 z:=cd[i]-rd[i];127 if z>0 then128 begin129 add(0,i,z div 2);130 add(i,0,0);131 s:=s+z div 2;132 end133 else begin134 add(i,t,-z div 2);135 add(t,i,0);136 end;137 end;138 if f then139 begin140 writeln('impossible');141 continue;142 end;143 if sap=s then writeln('possible') else writeln('impossible');144 end;145 end.