博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj1637
阅读量:6692 次
发布时间:2019-06-25

本文共 3586 字,大约阅读时间需要 11 分钟。

混合图欧拉回路

首先先明确基本概念
连通的无向图存在欧拉回路当且仅当不存在奇点
连通的有向图当且仅当每个点入度=出度
这道题我们显然应该当作连通的有向图来做
这个问题的困难之处在于我不知道应该从无向边的什么方向来走
那我们先假定一个走向,然后就变成了一个完全意义上的有向图,然后我们在进行调整
假定完方向后,我们就算出每个点的入度出度,
假如我们调整了了一条无向边的方向,那么对于一个端点入度会+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.
View Code

 

转载于:https://www.cnblogs.com/phile/p/4473121.html

你可能感兴趣的文章
[转载]android 显示多选列表对话框setMultiChoiceItems
查看>>
SVN Cleanup failed to process the following paths错误的解决
查看>>
使用button的:after伪类选择器内容的跳动
查看>>
Java从小白到入门,Day8,JAVAOO-多态
查看>>
CSS之各种居中
查看>>
poj 2594 Treasure Exploration
查看>>
bzoj千题计划297:bzoj3629: [JLOI2014]聪明的燕姿
查看>>
iOS简单实现毛玻璃效果
查看>>
maven学习(5)-Maven 聚合与继承特性
查看>>
可以设置命令执行的超时时间的脚本
查看>>
SQL server权限管理和备份实例
查看>>
sql server中的用户临时表和全局临时表的区别
查看>>
大整数算法[06] 绝对值加法
查看>>
2018-2019-1 20165325 《信息安全系统设计基础》第五周学习总结
查看>>
Python 列表(list)操作
查看>>
洛谷P1417 烹调方案
查看>>
Bzoj3652 大新闻
查看>>
GridView之数据邦定(HYPERLINK)小技巧与从数据库取汇总参数传值
查看>>
面试问题总结
查看>>
HTML特殊转义字符列表
查看>>